Calendar

LEC # TOPICS KEY DATES
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