CPS 102: Discrete Mathematics for Computer Science
| Instructor: Herbert Edelsbrunner |
| Teaching Assistant: Jie Xiao |
| announcements | schedule | references |
- January 13: our first class meeting.
| Date | Lecture Topic | Notes | Assignments |
| Jan 13 Wed | logistics | ||
| I. COUNTING | |||
| Jan 20 Wed | 01 Sets and list | Lecture [pdf] | |
| Jan 25 Mon | 02 Binomial coefficients | Lecture [pdf] | |
| Jan 27 Wed | 03 Equivalence relations | Lecture [pdf] | HW #1 [pdf] |
| Jan 29 Fri | recitation | ||
| II. NUMBER THEORY | |||
| Feb 01 Mon | 04 Modular arithmetic | Lecture [pdf] | |
| Feb 03 Wed | 05 Inverses | Lecture [pdf] | |
| Feb 05 Fri | recitation | ||
| Feb 08 Mon | 06 Euclid's algorithm | Lecture [pdf] | |
| Feb 10 Wed | 07 RSA cryptosystem | Lecture [pdf] | HW #2 [pdf] |
| Feb 12 Fri | recitation | ||
| Feb 15 Mon | first midterm | ||
| III. LOGIC | |||
| Feb 17 Wed | 08 Boolean algebra | Lecture [pdf] | |
| Feb 19 Fri | recitation | ||
| Feb 22 Mon | 09 Quantifiers | Lecture [pdf] | |
| Feb 24 Wed | 10 Inference | Lecture [pdf] | HW #3 [pdf] |
| Feb 26 Fri | recitation | ||
| IV. INDUCTION | |||
| Mar 01 Mon | 11 Mathematical induction | Lecture [pdf] | |
| Mar 03 Wed | 12 Recursion | Lecture [pdf] | |
| Mar 05 Fri | recitation | ||
| Mar 15 Mon | 13 Growth rates | Lecture [pdf] | |
| Mar 17 Wed | 14 Solving recurrence relations | Lecture [pdf] | HW #4 [pdf] |
| Mar 19 Fri | recitation | ||
| Mar 22 Mon | second midterm | ||
| V. PROBABILITY | |||
| Mar 29 Mon | 15 Inclusion-exclusion | Lecture [pdf] | |
| Mar 31 Wed | 16 Conditional probability | Lecture [pdf] | |
| Apr 02 Fri | recitation | ||
| Apr 05 Mon | 17 Random variables | Lecture [pdf] | |
| Apr 07 Wed | 18 Probability in hashing | Lecture [pdf] | |
| Apr 09 Fri | recitation | ||
| Apr 12 Mon | 19 Probability distributions | Lecture [pdf] | HW #5 [pdf] |
| VI. GRAPHS | |||
| Apr 14 Wed | 20 Trees | Lecture [pdf] | |
| Apr 16 Fri | recitation | ||
| Apr 19 Mon | 21 Tours | Lecture [pdf] | |
| Apr 21 Mon | 22 Matching | Lecture [pdf] | |
| Apr 23 Fri | recitation | ||
| Apr 26 Mon | 23 Planar graphs | Lecture [pdf] | HW #6 [pdf] |
| May 03 Mon | final exam at 7pm |
[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