Schedule

Problem sets are due at 10:00am 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: Logic
Date Due Class Topic Out Reading
1. M 9/15 Course overview; Math notation PS00; PS01 1, 3.1, 3.2, 3.3
2. W 9/17 Propositional logic; Truth tables; Logical equivalence PS02 [2.2.1–2.2.4, 2.6], 3.4, 3.5
3. F 9/19 PS00; PS01 Equivalence and transformation; Set notation; Predicates & quantifiers PS03 2.2.5–2.2.7, 4.1, 4.2, 4.3, p. 350
Week 2: Proofs
4. M 9/22 PS02 (Predicate-Logic) Theorems; Nested quantifiers; Proofs: why & how PS04 2.3, 2.4, 2.5, 5.1, 5.2, [5.3]
5. W 9/24 PS03 Proof techniques & strategies; Broken proofs PS05 5.3
6. F 9/26 PS04 More broken proofs; Mathematical induction PS06 5.4
Week 3: Recursion & Graphs
7. M 9/29 PS05 Recursive structures; The Fibonacci sequence PS07 11.1, 11.2
8. W 10/1 PS06 Induction review; Intro to Graphs PS08 11.3, 11.4, 11.5
9. F 10/3 PS07 PS06 Graphs PS09
Week 4: Interlude
Date Due Class Topic Out Reading
10. M 10/6 PS08 PS07 Trees; Graph traversal PS10
11. W 10/8 PS09 Graph representations; Series & convergence; Review
12. F 10/10 Exam 1 PS11 4.5, p. 729
Week 5: Codes
13. M 10/13 PS10 Error-correcting codes PS12 p. 730
14. W 10/15 PS11 Lab: Matrices and Hamming Codes PS13 6.1, 6.2, 6.3
15. F 10/17 PS12 Reed–Solomon codes; Secret-sharing; Mid-term evals PS14 6.4
Week 6: Asymptotics
XX. M 10/20 No class (like a Marxist utopia)
16. W 10/22 PS13 Efficiency & asymptotics basics (O/Ω/Θ) PS15 6.4
17. F 10/24 PS14 Running times for sorting algorithms PS16 9.1, 9.2
Week 7: Counting
Date Due Class Topic Out Reading
18. M 10/27 PS15 Running times for recursive algorithms PS17 9.3, 9.4
19. W 10/29 PS16 Counting in sets; Using functions to count PS18
20. F 10/31 PS17 Combinatorics
Week 8: Probability
21. M 11/3 Exam 2 PS19 10.1, 10.2
22. W 11/5 PS18 Combinatorial proofs; Pigeonhole principle; Probability intro PS20 10.3
23. F 11/7 PS19 Combining Events, Probability Distributions, Conditional Probability PS21 10.4
Week 9: Number Theory
24. M 11/10 PS19
PS20		 Bayes' Rule; Random variables and expectation PS22 7.1, 7.2
25. W 11/12 PS21 Cryptography; Modular arithmetic; Greatest common divisors PS23 7.3, 7.4
26. F 11/14 PS22 Division & exponentiation in modular arithmetic PS24 7.5; Cryptography blog post
 
Week 10: Cryptography
27. M 11/17 PS23 The RSA cryptosystem
28. W 11/19 PS24 Exponentiation in modular arithmetic; Fermat's Little Theorem; RSA redux; Course evals
Exam Period
Mon. 11/24 3a Exam Period: 8:30am–11am (though the final is self-scheduled)