CSCI 340-Discrete Computational Structures

CSCI 340: Discrete Computational Structures

Fall, 2005

Department of Computer Information Science

Indiana University—Purdue University, Indianapolis

Instructor: Dr. Yuanshun Dai

Course: Room No: LD027, M/W 4:00pm-5:15pm.

Instructor Office Hours: Monday: 3:00pm – 4:00 pm.

Room: SL280L

Phone: 317-274-3473

E-mail Address: YDai@cs.iupui.edu

TA- Xiaolong Wang, Office Hours: M/W 3:00-4:00pm.

Book: D.S. Malik and M.K. Sen, Discrete Mathematical Structures: Theory and Applications, Course Technology, 2004 (ISBN: 0619212853 and 0619215585)

DESCRIPTION:

This course is an introduction to Discrete Structures, which is an integral part of the computer science curriculum. In this course, we learn how theory and applications complement each other. We motivate proofs by presenting examples to show their relevance to the concept. Not only do we present proofs, we show how proofs are constructed. We do the same thing with algorithms – first show how the algorithm works, then formally present the algorithm. We provide a rich collection of exercises for each chapter, including a set of programming exercises.

PREREQUISITES: CSCI 240 and MATH 164..

GENERAL POLICY

You should make every effort to attend all lectures. Missed lecture notes should be obtained from fellow students. Handouts can be obtained from me personally or via electronic means. Exams will be announced approximately one week in advance. It is the responsibility of the student to notify the instructor in advance if the student cannot attend a regularly scheduled exam.

COURTESY

It is expected that students will conduct themselves in a courteous manner to the professor and fellow students. That includes no cell-phone calls, minimal talking in class, and no other actions that are disruptive to the class. Make every effort to arrive on time to class.

HOMEWORK POLICY

Assignments will normally be due one week after they are assigned. Assignments can be submitted up to one week late for half credit. Assignments submitted later than one week past the due date will receive no credit.

ATTENDANCE POLICY

Students are expected to attend ALL lecture sessions. Failure to attend may affect you grade. Students are responsible for material covered on the days they miss. Students are encouraged to actively participate in the class in a constructive manner.

GRADING

Exam 1 ------- 30%

Homework --------- 30%

Exam 2 -------- 30%

Attendance ------- 10%

-------

100%

Grading scale:

<50

>=50

>=55

>=60

>=65

>=70

>=73

>=77

>=80

>=83

>=87

>=90

>=95

D-

D+

C-

C+

B-

B+

A-

A+

SCHEDULE (The notes are subjected to change)

Class	Date	Day	Lecture	Notes	Chpt(s)	Due
1	8/24	W	Introduction		1
2	8/29	M	Sets	Lec1	1
3	8/31	W	Mathematical Logic	Lec2	1
4	9/7	W	Proof Techniques	Lec3	1 and 2
5	9/12	M	Relations I	Lec4	3	HW1
6	9/14	W	Relations II	Lec5	3
7	9/19	M	Matrices	Lec6	4
8	9/21	W	Functions I	Lec7	5
9	9/26	M	Functions II	Lec8	5	HW2
10	9/28	W	Counting Principles	Lec9	7
11	10/3	M	Discrete Probability	Lec10	7
12	10/5	W	Algorithms and Time Complexity I	Lec11	9	HW3
13	10/10	M	Algorithms and Time Complexity II	Lec12	9
14	10/12	W	Algorithms and Time Complexity III	Lec13	9
15	10/17	M	Review			HW4
16	10/19	W	Exam 1		1-7
17	10/24	M	Graph Theory I	Lec14	10
18	10/26	W	Graph Theory II	Lec15	10
19	10/31	M	Graph Theory III	Lec16	10
20	11/2	W	Trees and Networks I	Lec17	11
21	11/7	M	Trees and Networks II	Lec18	11	HW5
22	11/9	W	Boolean Algebra	Lec19	12
23	11/14	M	Combinatorial Circuits I	Lec20	12
24	11/16	W	Combinatorial Circuits II	Lec21	12	HW6
25	11/21	M	Finite Automata and Languages I	Lec22	13
26	11/28	M	Finite Automata and Languages II	Lec23	13
27	11/30	W	Review		9-13	HW7
28
Final	Dec 7		Exam 2		9-13