COMPSCI 102: Discrete Mathematics for Computer Science

CPS102: DISCRETE MATHEMATICS FOR COMPUTER SCIENCE

Term: Spring 2007

Lectures: Mo We 2:50pm - 4:05pm

Recitations: Fr 2:50pm - 4:05pm

Location: LSRC D243

Instructors:

Herbert Edelsbrunner

TA: Bei Wang, Office hour 5:00 p.m. - 7:00 p.m. Monday in D110, Email: beiwang AT cs.duke.edu

announcements schedule references

Announcements

January 10: first class meeting. This is a chance for us to get to know each other.
TA's email policy: please send email with the title CPS102; an email reply should be expected within 24 hours.
Monday (1/29/07) special office hour: 5:30 p.m. - 6:30 p.m. D110. Please email me if you would like to come.
The 1st homework can be turned in before 1/30/07 5:00 p.m. in D110. If the door is locked, please slide it under the door D110.
Notice: new TA office hour posted!
Late homework policy: Late homework will be accepted within 24 hours of the due date. Each student will be allowed one late submission without penalty. Or else you lose 25 points for turning in within 24 hours of the due date; 50 points penalty within 2 days after the due date; 75 points penalty within 3 days after the due date; no points afterwards.
Homework 1 has been graded, please stop by D110 to pick up your homework.
From TA: notice the changes to the HW2, I messed up the section number, sorry for the inconvinience.
From TA: Due to a meeting conflict, I have to move the office hour From Monday Feb 12, 5:00 p.m. to 7:00 p.m. to Tuesday Feb 13, from 5:00 p.m. to 7:00 p.m. If you have conflict, email and let me know, so we can figure out a special time Tuesday during the day, thank you.
HW2 has been graded, please pick up your homework in D110 on Tuesday between 5:00 - 7:00 p.m. Thank you.
From TA: Due to a class conflict, I have to move the office hour From Monday Feb 19, 5:00 p.m. to 7:00 p.m. to Wednesday Feb 21, from 5:00 p.m. to 7:00 p.m. If you have conflict, email and let me know, so we can figure out another time, thank you.
From TA: I have a talk to attend on 3/26/07 from 5:00 p.m. I am moving my office hour to Wed 3/28/07. Email and let me know if you have time conflict.
From TA: hw 5 has been graded. You can pick all your previous homework/midterms from my office. I have one HW5 with no name, please stop by my office to identify your hw.
From TA: I have all your graded homeworks in my office, please stop by to pick them up (otherwise I will leaving them outside my office starting next Monday). Please also stop by to check your homework grades as well.
From TA: I will have office hour Friday 3:00 - 4:00 p.m. D110. Last office hour of the semester. Good luck with your finals!
Practice Exam has been posted. The hint/solution will be posted late Friday / early Saturday.
From TA: HW 6 has been graded. You can pick up your hw in D110. Everyone should receive an email with summary of his/her hw/midterm points, if you have not received an email in your duke account, please let me know ASAP (before Wednesday next week). If there is a problem, please let me know ASAP.
From TA: The hint to the practice exam has been posted.
From TA: the second question in the Practice exam has been updated, solution posted.

Schedule

Date Lecture Topic Notes Assignments
Jan 10 Wed logistics

I. COUNTING
Jan 17 Wed sets and list
read Sections 1.1 and 1.2 HW#1a: Sec. 1.1 Problem 13; Sec. 1.2 Problem 13
Jan 22 Mon binomial coefficients
read Section 1.3 HW#1b: Sec. 1.3 Problem 3 (b) (c), Problem 18
Jan 24 Wed equivalence relations
read Section 1.4 HW#1c [pdf]
Jan 26 Fri Recitation
Rec 2 [pdf] Rec 2 Solutions [pdf]

II. NUMBER THEORY
Jan 29 Mon modular arithmetic
HW#1 due; Solutions [pdf] HW#2a: Sec 2.1 Problem 8, Problem 12 (a)
Jan 31 Wed inverses
read Sections 2.1 and 2.2 HW#2b: Sec 2.2 Problem 2, Problem 14
Feb 02 Fri Recitation
Rec 3 [pdf] Rec 3 Solutions [pdf]
Feb 05 Mon Euclid's algorithm
read Section 2.2 HW#2c: Sec 2.2 Problem 12, Problem 22
Feb 07 Wed RSA cryptosystems
read Section 2.3 HW#2d: Sec 2.3 Problem 2, Problem 12
Feb 12 Mon primality testing
HW#2 due; Solutions [pdf] read Section 2.4
Feb 14 Wed first midterm
III. LOGIC
Feb 19 Mon equivalences and implications
read Section 3.1 HW#3a: Sec 3.1, Problem 6, Problem 8
Feb 21 Wed variables and quantifiers
read Section 3.2 HW#3b: Sec 3.2, Problem 2, Problem 9
Feb 26 Mon inference
read Section 3.3 HW#3c: Sec 3.3, Problem 2 and 3.
IV. INDUCTION
Feb 28 Wed mathematical induction
read Section 4.1, HW#3 due HW#4a: Sec 4.1, Problem 2, Problem 4
Mar 05 Mon recursion
read Section 4.2 HW#4b: Sec 4.2, Problem 13, Problem 15
Mar 07 Wed growth rates
read Section 4.3 HW#4c: Sec 4.3, Problem 1, Problem 4
Mar 09 Fri recitation
Sec 4.3, Problem 7, Problem 9 (a)
Mar 19 Mon Master Theorem
read Section 4.4 HW#4d: Sec 4.4, Problem 2, Problem 4
Mar 21 Wed selection
read Section 4.6, HW#4 due
Mar 26 Mon second midterm
V. PROBABILITY
Mar 28 Wed inclusion-exclusion
read Sections 5.1 and 5.2 HW#5a: Sec 5.2, Problem 2, Problem 10
Apr 02 Mon conditional probability
read Section 5.3 HW#5b: Sec 5.3, Problem 2, Problem 6
Apr 04 Wed random variables
read Section 5.4 HW#5c: Sec 5.4, Problem 4, Problem 19
Apr 09 Mon probability in hashing
read Section 5.5 HW#5d: Sec 5.5, Problem 4, Problem 14
Apr 11 Wed probability distributions
read Section 5.7 HW#5e: Sec 5.7, Problem 2, Problem 8

VI. GRAPHS
Apr 16 Mon trees
read Sections 6.1 and 6.2, HW#5 due HW#6a: Section 6.1, Problem 6, Problem 14
Apr 18 Wed tours
read Section 6.3 HW#6b: Section 6.3, Problem 2, Problem 10
Apr 23 Mon matching
read Section 6.4 HW#6c: Section 6.4, Problem 12, Problem 14
Apr 25 Wed planarity
read Section 6.5 HW#6 due
Apr 26 Thur Practice Exam
[pdf] [solution pdf]
May 03 Thu final exam from 7-10pm

References

[1] Bogart, Stein, Drysdale. Discrete Mathematics for Computer Science. Key College Publishing, Emeryville, California, 2006.

[2] Rosen. Discrete Mathematics and Its Applications. Fourth edition, WCB, McGraw-Hill, Boston, Massachusetts, 1999.

[3] Graham, Knuth, Patashnik. Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts, 1999.

[4] Matousek, Nesetril. Invitation to Discrete Mathematics. Claredon Press, Oxford, England, 1998.

announcements schedule references

Herbert Edelsbrunner (edels@cs.duke.edu) January 2007

Date	Lecture Topic	Notes	Assignments
Jan 10 Wed	logistics
	I. COUNTING
Jan 17 Wed	sets and list	read Sections 1.1 and 1.2	HW#1a: Sec. 1.1 Problem 13; Sec. 1.2 Problem 13
Jan 22 Mon	binomial coefficients	read Section 1.3	HW#1b: Sec. 1.3 Problem 3 (b) (c), Problem 18
Jan 24 Wed	equivalence relations	read Section 1.4	HW#1c [pdf]
Jan 26 Fri	Recitation	Rec 2 [pdf]	Rec 2 Solutions [pdf]
	II. NUMBER THEORY
Jan 29 Mon	modular arithmetic	HW#1 due; Solutions [pdf]	HW#2a: Sec 2.1 Problem 8, Problem 12 (a)
Jan 31 Wed	inverses	read Sections 2.1 and 2.2	HW#2b: Sec 2.2 Problem 2, Problem 14
Feb 02 Fri	Recitation	Rec 3 [pdf]	Rec 3 Solutions [pdf]
Feb 05 Mon	Euclid's algorithm	read Section 2.2	HW#2c: Sec 2.2 Problem 12, Problem 22
Feb 07 Wed	RSA cryptosystems	read Section 2.3	HW#2d: Sec 2.3 Problem 2, Problem 12
Feb 12 Mon	primality testing	HW#2 due; Solutions [pdf] read Section 2.4
Feb 14 Wed		first midterm
	III. LOGIC
Feb 19 Mon	equivalences and implications	read Section 3.1	HW#3a: Sec 3.1, Problem 6, Problem 8
Feb 21 Wed	variables and quantifiers	read Section 3.2	HW#3b: Sec 3.2, Problem 2, Problem 9
Feb 26 Mon	inference	read Section 3.3	HW#3c: Sec 3.3, Problem 2 and 3.
	IV. INDUCTION
Feb 28 Wed	mathematical induction	read Section 4.1, HW#3 due	HW#4a: Sec 4.1, Problem 2, Problem 4
Mar 05 Mon	recursion	read Section 4.2	HW#4b: Sec 4.2, Problem 13, Problem 15
Mar 07 Wed	growth rates	read Section 4.3	HW#4c: Sec 4.3, Problem 1, Problem 4
Mar 09 Fri	recitation		Sec 4.3, Problem 7, Problem 9 (a)
Mar 19 Mon	Master Theorem	read Section 4.4	HW#4d: Sec 4.4, Problem 2, Problem 4
Mar 21 Wed	selection	read Section 4.6, HW#4 due
Mar 26 Mon		second midterm
	V. PROBABILITY
Mar 28 Wed	inclusion-exclusion	read Sections 5.1 and 5.2	HW#5a: Sec 5.2, Problem 2, Problem 10
Apr 02 Mon	conditional probability	read Section 5.3	HW#5b: Sec 5.3, Problem 2, Problem 6
Apr 04 Wed	random variables	read Section 5.4	HW#5c: Sec 5.4, Problem 4, Problem 19
Apr 09 Mon	probability in hashing	read Section 5.5	HW#5d: Sec 5.5, Problem 4, Problem 14
Apr 11 Wed	probability distributions	read Section 5.7	HW#5e: Sec 5.7, Problem 2, Problem 8
	VI. GRAPHS
Apr 16 Mon	trees	read Sections 6.1 and 6.2, HW#5 due	HW#6a: Section 6.1, Problem 6, Problem 14
Apr 18 Wed	tours	read Section 6.3	HW#6b: Section 6.3, Problem 2, Problem 10
Apr 23 Mon	matching	read Section 6.4	HW#6c: Section 6.4, Problem 12, Problem 14
Apr 25 Wed	planarity	read Section 6.5	HW#6 due
Apr 26 Thur	Practice Exam	[pdf]	[solution pdf]
May 03 Thu		final exam from 7-10pm

[1]	Bogart, Stein, Drysdale. Discrete Mathematics for Computer Science. Key College Publishing, Emeryville, California, 2006.
[2]	Rosen. Discrete Mathematics and Its Applications. Fourth edition, WCB, McGraw-Hill, Boston, Massachusetts, 1999.
[3]	Graham, Knuth, Patashnik. Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts, 1999.
[4]	Matousek, Nesetril. Invitation to Discrete Mathematics. Claredon Press, Oxford, England, 1998.