Week 1 |
1 | Good and bad proofs | |
2 | Proof by contradiction | |
Week 2 |
3 | Well ordering principle | |
4 | Propositional logic | |
5 | Sets and relations | Problem set 1 due |
Week 3 |
6 | Size of sets, mapping lemma | |
7 | Predicates and quantifiers | Mini-quiz 1 |
8 | Set theory, Russell paradox | Problem set 2 due |
Week 4 |
9 | Induction and strong induction | |
10 | Partial orders | |
11 | Partial orders and scheduling | Problem set 3 due |
Week 5 |
12 | Digraphs | |
13 | State machines, preserved invariants | Mini-quiz 2 |
14 | Derived variables, termination | Problem set 4 due |
Week 6 |
15 | Stable matching | |
16 | Simple graphs, degrees, isomorphism | |
17 | Graph connectedness, trees | Problem set 5 due |
Week 7 |
18 | Graph coloring, bipartite matching | |
19 | Recursive data | Mini-quiz 3 |
20 | Planar graphs | Problem set 6 due |
Week 8 |
21 | GCD and integer linear combinations | |
22 | Modular arithmetic | |
23 | Inverses (mod n), RSA encryption | Problem set 7 due |
Week 9 |
24 | Harmonic sums, Stirling's approximation | |
25 | Asymptotics | Mini-quiz 4 |
26 | Counting with bijections | Problem set 8 due |
Week 10 |
27 | Pigeonhole and division rules | |
28 | Counting repetitions, card magic | |
29 | Inclusion-exclusion, counting practice | Problem set 9 due |
Week 11 |
30 | Binomial theorem, combinatorial identities | Mini-quiz 5 |
31 | Generating functions: for counting | Problem set 10 due |
Week 12 |
32 | Generating functions: for recurrences | |
33 | Introduction to probability | |
34 | Conditional probability, independence | Problem set 11 due |
Week 13 |
35 | Random variables | |
36 | Expectation | Mini-quiz 6 |
37 | Variance | Problem set 12 due |
Week 14 |
38 | Sampling and confidence | |
39 | Random processes | |