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

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