CPS 102: Discrete Mathematics for Computer Science

Term: Spring 2009
Time: Mon Wed Fri 2:50 - 4:05
Location: D243 LSRC
Co-instructors: Herbert Edelsbrunner and Brittany Fasy

announcements schedule references

Announcements

Schedule

Date Lecture Topic Notes Assignments
Jan 07 Wed logistics
   
  I. COUNTING    
Jan 12 Mon 1 Sets and list
Lecture [pdf]  
Jan 14 Wed 2 Binomial coefficients
Lecture [pdf]  
Jan 16 Fri recitation
   
Jan 21 Wed 3 Equivalence relations
Lecture [pdf] HW #1 [pdf]
Jan 23 Fri recitation
   
  II. NUMBER THEORY    
Jan 26 Mon 4 Modular arithmetic
Lecture [pdf]  
Jan 28 Wed 5 Inverses
Lecture [pdf]  
Jan 30 Fri recitation
   
Feb 02 Mon 6 Euclid's algorithm
Lecture [pdf]  
Feb 04 Wed 7 RSA cryptosystem
Lecture [pdf] HW #2 [pdf]
Feb 6 Fri recitation
   
  III. LOGIC    
Feb 09 Mon 8 Boolean algebra
Lecture [pdf]  
Feb 11 Wed first midterm   Solutions [pdf]
Feb 16 Mon 9 Quantifiers
Lecture [pdf]  
Feb 18 Wed 10 Inference
Lecture [pdf] HW #3 [pdf]
Feb 20 Fri recitation
   
  IV. INDUCTION    
Feb 23 Mon 11 Mathematical induction
Lecture [pdf]  
Feb 25 Wed 12 Recursion
Lecture [pdf]  
Feb 27 Fri recitation
   
Mar 04 Wed 13 Growth rates
Lecture [pdf]  
Mar 16 Mon 14 Solving recurrence relations
Lecture [pdf] HW #4 [pdf]
  V. PROBABILITY    
Mar 18 Wed 15 Inclusion-exclusion
Lecture [pdf]  
Mar 20 Fri recitation
   
Mar 23 Mon second midterm   Solutions [pdf]
Mar 25 Wed 16 Conditional probability
Lecture [pdf]  
Mar 27 Fri recitation
   
Mar 30 Mon 17 Random variables
Lecture [pdf]  
Apr 01 Wed 18 Probability in hashing
Lecture [pdf]  
Apr 03 Fri recitation
   
Apr 06 Mon 19 Probability distributions
Lecture [pdf] HW #5 [pdf]
  VI. GRAPHS    
Apr 08 Wed 20 Trees
Lecture [pdf]  
Apr 10 Fri recitation
   
Apr 13 Mon 21 Tours
Lecture [pdf]  
Apr 15 Wed 22 Matching
Lecture [pdf]  
Apr 17 Fri recitation
   
Apr 20 Mon 23 Planar graphs
Lecture [pdf] HW #6 [pdf]
Apr 22 Wed review
All Lectures [pdf]  
Apr 29 Wed final exam 7-10pm   Solutions [pdf]

References

[1] Bogart, Stein and 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 and Patashnik. Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts, 1989.
[4] Matousek and Nesetril. Invitation to Discrete Mathematics. Claredon Press, Oxford, England, 1998.

announcements schedule references


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