Problem sets are due at 1:30pm on the day indicated. Reading assignments are listed on the day they are assigned, and generally prepare you for the next class. Readings to skim are in brackets. Note that this schedule is an aspirational approximation of what we'll do; it may be updated as the term goes on.
| Week 1: Intro; Logic | ||||
| Date | Due | Class Topic | Out | Reading |
|---|---|---|---|---|
| 1. M 3/30 | Course overview; Math notation | PS00; PS01 | 1, 2.2, 2.3, 2.4–2.4.1 | |
| 2. W 4/1 | Background grab-bag | PS02 | 3.1–3.3 | |
| 3. F 4/3 | PS00; PS01 | Propositional logic; Truth tables; Circuits | PS03 | 2.5, 3.4, 3.5 |
| Week 2: Logic; Proofs | ||||
| 4. M 4/6 | PS02 | Equivalence and transformation; Predicates | PS04 | p. 346 |
| 5. W 4/8 | PS03 | Predicates & quantifiers; (Predicate-Logic) Theorems; Nested quantifiers | PS05 | 4.3–4.5 |
| 6. F 4/10 | PS04 | Proofs: why & how; Proof techniques & strategies | PS06 | 5.1, 5.2, [5.3] |
| Week 3: Proofs; Induction; Recursion | ||||
| 7. M 4/13 | PS05 | More proof techniques; Broken proofs | PS07 | 5.3, 5.4 |
| 8. W 4/15 | PS06 | Mathematical induction | PS08 | 2.4.2 |
| 9. F 4/17 | PS07 | More on Induction; Recursive structures
|
PS09 | 11.1, 11.2, 11.3 |
| Week 4: Graphs | ||||
| Date | Due | Class Topic | Out | Reading |
| 10. M 4/20 | PS08 | Induction review; Graphs & Trees | PS10 | 11.4, 11.5 |
| 11. W 4/22 | PS09 | More Graphs &s Trees; Graph traversal | ||
| 12. F 4/24 | Exam 1 | PS11 | 4.2, pp. 729 & 730 | |
| Week 5: Codes | ||||
| 13. M 4/27 | PS10 | Graph traversal; Graph representations; Course feedback | PS12 | 2.2 & 2.4 |
| 14. W 4/29 | PS11 | Error-correcting codes | PS13 | |
| 15. F 5/1 | PS12 | Lab: Matrices and Hamming Codes | 6.1–6.4 | |
| Week 6: Asymptotics | ||||
| XX. M 5/4 | No class (like a Marxist utopia) | |||
| 16. W 5/6 | PS13 | Efficiency & asymptotics basics (O/Ω/Θ) | PS15 | 6.4 |
| 17. F 5/8 | Running times for sorting algorithms | PS16 | ||
| Week 7: Counting | ||||
| Date | Due | Class Topic | Out | Reading |
| 18. M 5/11 | PS15 | Running times for recursive algorithms | 9.1, 9.2 | |
| 19. W 5/13 | PS16 | Counting in sets; Using functions to count | PS18 | 9.3, 9.4 |
| 20. F 5/15 | Pigeonhole principle; Combinatorics | PS19 | ||
| Week 8: Probability | ||||
| 21. M 5/18 | PS18 | Combinatorial proofs; Probability distributions; Outcomes
|
PS20 | 10.1, 10.2 |
| 22. W 5/20 | PS19 | Events; Combining events; Probability distributions redux; Conditional probability | 10.3 | |
| 23. F 5/22 | Exam 2, proctored by Amy | PS21 | 10.4 | |
| Week 9: Number Theory | ||||
| 24. M 5/25 | PS20 | Bayes' Rule; Random variables and expectation | 7.1, 7.2 | |
| 25. W 5/27 | PS21 | Cryptography; Divisibility | PS23 | 7.3, 7.4 |
| 26. F 5/29 | Divisibility; Modular arithmetic; Greatest common divisors; Division in modular arithmetic | PS24 | 7.5; Cryptography blog post | |
| Week 10: Cryptography | ||||
| 27. M 6/1 | PS23 | Time complexity of the Euclidean Algorithm; Multiplicative inverses and the Extended Euclidean Algorithm | ||
| 28. W 6/3 | PS24 | Exponentiation in modular arithmetic; Fermat's Little Theorem; RSA redux; Course evals | ||
| Exam Period | ||||
| Sun. 6/7 | 5a Exam Period: 3:30pm–6pm (though the final is self-scheduled) | |||