Calendar
The textbooks for this course are optional and both can be found online for free either courtesy of Duke libraries or via a free pdf.
- FDM: Tom Jenkyns and Ben Stephenson, Fundamentals of Discrete Math for Computer Science, Springer, 2013.
- MCS: Eric Lehman, F Thomson Leighton, and Albert R Meyer, Mathematics for Computer Science
The syllabus below is a plan, not a commitment. Depending on the time needed to cover the various topics, it may be necessary to skip, rearrange, or substitute some of the material listed.
As we cover topics, we will mark where in the two books further study material can be found.
All materials are optional unless explicitly marked as required below.
Materials from FDM are given in the form of page ranges, and materials from MCS are given in the form of section numbers. Pages or sections in parentheses are good to know but may or may not be covered. The following schedule is based off of this google sheet.
Please see this table for full detail regarding the course collaboration policy.
Find lecture notes and homeworks (and solutions, when the time comes) on Sakai.
| 0 | Introduction |
| Date | Topic | FDM | MCS | Other Materials | HW Due |
|---|---|---|---|---|---|
| Wed 5/13 (Lec 1) | Logistics, Warmup | — | — | LaTeX Intro | — |
| Thur 5/14 (Rec) | Introduction to Recitation | — | — | — | — |
| 1 | Logic and Proofs |
| Date | Topic | FDM | MCS | Other Materials | HW Due |
|---|---|---|---|---|---|
| Thur 5/14 (Lec 2) | Logic | 1-29 (optional); 77-89 | 1.1-1.9 | Carlo's Notes on Logic | — |
| Mon 5/18 (Lec 3) | Logic and Proofs | 1-29 (optional); 77-89 | 2.1-2.4 | Stanley Chang's Notes on Logic | — |
| Tues 5/19 (Rec) | Playing with Proofs | 89-95 | — | — | — |
| Tues 5/19 (Lec 4) | Proofs (including contradiction) | 89-95 | 3.1-3.6 | — | — |
| Wed 5/20 (Lec 5) | Proofs by Induction | 89-95 | 5.1-5.2 | — | HW 1 Due |
| Thur 5/21 (Rec) | Recursion, WOP, and Proofs | 89-95 | — | — | — |
| Thur 5/21 (Lec 6) | Proofs by Induction (contd) | 89-95 | 7.1 & 7.6 (8.4) | — | — |
| Mon 5/25 (NONE) | No Class: Memorial Day | — | — | — | — |
| Tues 5/26 (Rec) | More Playing with Proofs | — | — | — | — |
| 2 | Set Theory; Relations and Functions |
| Date | Topic | FDM | MCS | Other Materials | HW Due |
|---|---|---|---|---|---|
| Tues 5/26 (Lec 7) | Primes and Sets | 1-29; 43-54 | 4.1-4.4 | — | — |
| Wed 5/27 (Lec 8) | Sets and Functions | 1-29; 43-54 | 4.1-4.4 | — | Homework 2 Due |
| Thur 5/28 (Rec) | Drawing Maps | — | — | — | — |
| Thur 5/28 (Lec 9) | Relations and Functions | 1-29; 43-54 | 10.6; 10.10-10.11 | — | — |
| Mon 6/1 (Lec 10) | Infinity and Relations | 1-29; 43-54 | 10.10-10.11 | — | HW 3A Due Monday 11:59PM EST |
| Tuesday 6/2 (Rec) | Special Lecture - Partial Orders | — | — | — | — |
| Tuesday 6/2 (Lec 11) | Infinity and Counting | 8.1, 8.2, 14.1, | — | — | — |
| Wednesday 6/3 (Lec 12) | Counting and Probability | 14.3,14.5 | 54-64 | — | — |
| Thursday 6/4 (Rec) | MIDTERM (Lec 1-9, start of 10) | — | — | — | — |
| 2 | Counting and Probability |
| Date | Topic | FDM | MCS | Other Materials | HW Due |
|---|---|---|---|---|---|
| Thurs 6/4 (Lec 13) | Probability | 54-64 | 15.1, 15.3 | — | — |
| Monday 6/8 (Lec 14) | Probability | 54-64 | 15.3 | — | — |
| Tues 6/9 (Rec) | Playing with Probability (1) | 54-64 | 15.5 | — | — |
| Tues 6/9 (Lec 15) | Probability | 351-375 | chapter 17 | — | — |
| Wed 6/10 (Lec 16) | Probability and Hashing | 351-375 | 18.1-18.8 | — | HW 4 DUE |
| Thurs 6/11 (Rec) | Playing with Probability (2) | 351-375 | 19.1-19.5 | — | — |
| Thurs 6/11 (Lec 17) | More Probability | 351-375 | 20.1-20.3 | — | — |
| 2 | Graph Theory |
| Date | Topic | FDM | MCS | Other Materials | HW Due |
|---|---|---|---|---|---|
| Mon 6/15 (Lec 18) | Trees | 131-136 & 183-203 | 12.1-12.3 | — | — |
| Tues 6/16 (Rec) | Medley | 131-136 & 183-203 | — | — | — |
| Tues 6/16 (Lec 19) | Graphs and Trees | 131-136 & 183-203 | 12.5-12.8 | — | — |
| Wed 6/17 (Lec 20) | Coloring and More | 131-136 & 183-203 | 12.11 | — | HW 5 DUE (11:59 pm) |
| Thurs 6/18 (Rec) | Graphs and Trees Practice | 131-136 & 183-203 | — | — | — |
| Thurs 6/18 (Lec 21) | More Coloring | 131-136 & 183-203 | 10.1-10.2 | — | — |
| Mon 6/22 (Lec 22) | DAGs and Leftovers | 131-136 & 183-203 | 10.5 | — | HW 6A DUE (11:59 pm) |
| Thurs 6/25 | FINAL EXAM 2- 5 PM | — | — | EXACT TIME SUBJECT TO CHANGE | — |
COMPSCI , Duke University, Site based on Professor Carlo Tomasi's 230 website