Home Calendar Staff Grades FAQ Policies
 Week Date Day Lecture Topic Available Due 1 Aug25 M Recitation 1 (Latex) Aug26 T 1 (VA) Pancakes with a Problem Lecture slides [PDF] Notes on Pancakes Aug28 R 2 (VA) Inductive Reasoning: One Step at a Time Lecture slides [PDF] Notes on Induction: 1, 2, 3. Notes on common induction mistakes Hwk1 2 Sep1 M NO CLASSES Sep2 T 3 (VG) Logic: Axiomatic Systems, Propositional Calculus, First Order Logic. Lecture slides [PPS, PDF] Notes on Propositional Formulas Notes on first order logic Sep4 R 4 (VG) Proofs Lecture slides [PPS, PDF] Notes on proof methods Hwk2 Hwk1 [Solutions] 3 Sep8 M Recitation 2 (Logic) Solutions Sep9 T 5 (VG) Counting I Lecture slides [PDF] Notes on Counting Sep11 R 6 (VG) Counting II. Lecture slides [PDF] Hwk3 Hwk2 [Solutions] 4 Sep15 M Recitation 3 (Counting) Solutions Sep16 T 7 (VG) Generating Functions Lecture slides [PDF] Notes on generating functionss More notes on generating functions Sep18 R 8 (VG) Combinatorial Games Lecture slides [PDF] Notes on Games Hwk4 Hwk3 [Solutions] 5 Sep22 M Recitation 4 (Generating Functions and Combinatorial Games) Solutions Sep23 T 9 (VA) Probability - I Lecture slides [PDF] Notes on probability Sep25 R 10 (VA) Probability - II Lecture slides [PDF] Notes on random variables Hwk5 Hwk4 [Solutions] 6 Sep29 M Recitation 5 (Probability) Solutions Sep30 T TEST 1 Practice Test [Solutions] Oct2 R 11 (VA) Graphs - I Lecture notes [PDF] Notes on Graphs I Further notes on basics of graphs 7 Oct6 M Recitation 6 (Graphs) Solutions Oct7 T 12 (VA) Graphs - II Lecture slides [PDF] Notes on Graphs II Notes on Planar Graphs Hwk6 Hwk5 [Solutions] Oct9 R 13 (VA) Graphs - III Lecture slides [PDF] 8 Oct13 M Recitation 7 (Graphs) Solutions Oct14 T 14 (VG) Group Theory Lecture slides [PDF] Notes on group theory Oct16 R 15 (VG) Fields, Polynomials Lecture slides [PDF] Notes on polynomials, error correction Hwk7 Hwk6 [Solutions] 9 Oct20 M Recitation 8 (Polynomials and Groups) Solutions Oct21 T 16 (VA) Random Walks [PDF] Oct23 R 17 (VG) Error Correction Lecture slides [PDF] [PPS] Notes: Sections 5 here and here Hwk8 Hwk7 [Solutions] 10 Oct27 M Recitation 9 (Random Walks, Error Correction) Solutions Oct28 T 18 (VG) Public Key Cryptography Lecture slides [PDF] Oct30 R 19 (VA) Finite State Automata [PDF] Hwk8 [Solutions] 11 Nov3 M Recitation 10 (Crypto and FSAs) Solutions Nov4 T TEST 2 Practice Test [Solutions] Nov6 R 20 (VA) Cantor's Legacy: Infinity And Diagonalization [PDF] Hwk9 12 Nov10 M Recitation 11 (FSA) Solutions Nov11 T 21 (VA) Turing and Church's Legacy: The Limits of Computation [PDF] Nov13 R 22 (VG) Godel's Legacy: Truth vs. Proof Lecture slides [PDF] Hwk10 Hwk9 [Solutions] 13 Nov17 M Recitation 12 (Turing Machines) Solutions Nov18 T 23 (VG) Efficient reductions Lecture slides [PDF] Nov20 R 24 (VG) P vs NP Lecture slides [PDF] Hwk11 Hwk10 [Solutions] 14 Nov24 M Recitation 13 (Reductions) Solutions Nov25 T 25 (VA) Approximation algorithms Lecture notes [PDF] Nov27 R No classes 15 Dec01 M Recitation 14 (Solutions) ( ) Dec02 T 26 (VG) Interactive/Zero Knowledge Proofs Lecture slides [PDF] Hwk11 [Solutions] Dec04 R 27 (VA) Epilogue/special topic Lecture slides [PDF]