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 |
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] |
[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 |