
Week  Date  Day  Lecture  Topic  Available  Due 
1  Aug 25 
M  Recitation 1 (Latex)  
Aug 26 
T  1 (VA)  Pancakes with a Problem
Lecture slides [PDF] Notes on Pancakes 

Aug 28 
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  Sep 1 
M  NO CLASSES  
Sep 2 
T  3 (VG)  Logic: Axiomatic Systems, Propositional Calculus, First Order Logic.
Lecture slides [PPS, PDF] Notes on Propositional Formulas Notes on first order logic 

Sep 4 
R  4 (VG)  Proofs
Lecture slides [PPS, PDF] Notes on proof methods 
Hwk2  Hwk1 [Solutions]  
3  Sep 8 
M 
Recitation 2 (Logic)
Solutions 

Sep 9 
T  5 (VG)  Counting I
Lecture slides [PDF] Notes on Counting 

Sep 11 
R  6 (VG)  Counting II.
Lecture slides [PDF] 
Hwk3  Hwk2 [Solutions]  
4  Sep 15 
M 
Recitation 3 (Counting)
Solutions 

Sep 16 
T  7 (VG)  Generating Functions
Lecture slides [PDF] Notes on generating functionss More notes on generating functions 

Sep 18 
R  8 (VG)  Combinatorial Games Lecture slides [PDF] Notes on Games 
Hwk4 
Hwk3 [Solutions]  
5  Sep 22 
M 
Recitation 4 (Generating Functions and Combinatorial Games) Solutions 

Sep 23 
T  9 (VA)  Probability  I Lecture slides [PDF] Notes on probability 

Sep 25 
R  10 (VA)  Probability  II
Lecture slides [PDF] Notes on random variables 
Hwk5  Hwk4 [Solutions]  
6  Sep 29 
M 
Recitation 5 (Probability) Solutions 

Sep 30 
T  TEST 1
Practice Test [Solutions] 

Oct 2 
R  11 (VA)  Graphs  I Lecture notes [PDF] Notes on Graphs I Further notes on basics of graphs 

7  Oct 6 
M  Recitation 6
(Graphs)
Solutions 

Oct 7 
T  12 (VA)  Graphs  II Lecture slides [PDF] Notes on Graphs II Notes on Planar Graphs 
Hwk6  Hwk5 [Solutions]  
Oct 9 
R  13 (VA)  Graphs  III Lecture slides [PDF] 

8  Oct 13 
M  Recitation 7
(Graphs)
Solutions 

Oct 14 
T  14 (VG)  Group Theory
Lecture slides [PDF] Notes on group theory 

Oct 16 
R  15 (VG) 
Fields, Polynomials
Lecture slides [PDF] Notes on polynomials, error correction 
Hwk7  Hwk6 [Solutions]  
9  Oct 20 
M  Recitation 8 (Polynomials and Groups)
Solutions 

Oct 21 
T  16 (VA)  Random Walks
[PDF] 

Oct 23 
R  17 (VG)  Error Correction Lecture slides [PDF] [PPS] Notes: Sections 5 here and here 
Hwk8  Hwk7 [Solutions]  
10  Oct 27 
M  Recitation 9 (Random Walks, Error Correction)
Solutions 

Oct 28 
T  18 (VG)  Public Key Cryptography Lecture slides [PDF] 

Oct 30 
R  19 (VA) 
Finite State Automata
[PDF] 
Hwk8 [Solutions]  
11  Nov 3 
M  Recitation 10 (Crypto and FSAs)
Solutions 

Nov 4 
T  TEST 2
Practice Test [Solutions] 

Nov 6 
R  20 (VA)  Cantor's Legacy: Infinity And Diagonalization [PDF]  Hwk9  
12  Nov 10 
M 
Recitation 11 (FSA)
Solutions 

Nov 11 
T  21 (VA)  Turing and Church's Legacy: The Limits of Computation [PDF]  
Nov 13 
R  22 (VG)  Godel's Legacy: Truth vs. Proof
Lecture slides [PDF] 
Hwk10  Hwk9 [Solutions]  
13  Nov 17 
M  Recitation 12 (Turing Machines)
Solutions 

Nov 18 
T  23 (VG)  Efficient reductions
Lecture slides [PDF] 

Nov 20 
R  24 (VG)  P vs NP
Lecture slides [PDF] 
Hwk11  Hwk10 [Solutions]  
14  Nov 24 
M 
Recitation 13 (Reductions)
Solutions 

Nov 25 
T  25 (VA)  Approximation algorithms Lecture notes [PDF] 

Nov 27 
R  No classes  
15  Dec 01 
M  Recitation 14 (Solutions) ( )  
Dec 02 
T  26 (VG)  Interactive/Zero Knowledge Proofs Lecture slides [PDF] 
Hwk11 [Solutions]  
Dec 04 
R  27 (VA) 
Epilogue/special topic
Lecture slides [PDF] 