
Week  Date  Day  Lecture  Topic  Available  Due 
1  Jan 12 
M  No Recitations  
Jan 13 
T  1 (L)  Solving Problems, Writing Proofs and Enjoying the Pain: How to Succeed in 251 [ PPT  PDF ]  Hwk1  Individual Part  
Jan 15 
R  2 (L)  Pancakes with a Problem [ PPT  PDF ] 

2  Jan 19 
M  MLK DAY: No Recitations  
Jan 20 
T  3 (L)  Inductive Reasoning
[ PPT  PDF ] Induction Dos and Don'ts 
Hwk2  Solutions to Warmup  Hwk1 Sols  
Jan 22 
R  4 (L) 
Games: Which Player Wins?
[ PPT  PDF ]
Quiz 1 

3  Jan 26 
M  Recitation 1 Problems  Solutions 

Jan 27 
T  5 (A)  Ancient Wisdom: Choose your Representation, Unary and Binary [ PPT  PDF ] 
Hwk3  Solutions to Warmup  Hwk2 Sols  
Jan 29 
R  6 (A)  Counting I: Choice Trees and Correspondences [ PPT  PDF ] 

4  Feb 2 
M  Recitation 2 Problems  Solutions 

Feb 3 
T  7 (A)  Counting II: Pigeons, Pirates and Pascal [ PPT  PDF ] 
Hwk4  Solutions to Warmup  Hwk3 Sols  
Feb 5 
R  8 (A)  Counting III: Generating Functions Quiz 2 [ PPT  PDF ] GF Handouts from Fall 08 [1], [2] 

5  Feb 9 
M  Recitation 3 Problems  Solutions 

Feb 10 
T  9 (L)  Primes, GCD, and Continued Fractions [ PPT  PDF ] 
Hwk5  Practice Test  Solutions to Warmup  Hwk4 Sols  
Feb 12 
R  10 (L)  The Math of the 1950's Dating [ PPT  PDF ] 

6  Feb 16 
M  Recitation 4: TEST 1
[Practice Test Solutions]
[Additional Practice Test (NOT part of assignment 5)  Solutions] 

Feb 17 
T  11 (L)  Probability I [ PPT  PDF ] 

Feb 19 
R  12 (L)  Probability II [ PPT  PDF ] 
Hwk6  Solutions to Warmup  Hwk5 Sols  
7  Feb 23 
M 
Recitation 5 Problems  Solutions 

Feb 24 
T  13 (A)  Number Theory [ PPT  PDF ] Quiz 3 

Feb 26 
R  14 (A)  Cryptography and RSA [ PPT  PDF ]  Hwk7  Solutions to Warmup  Hwk6 Sols  
8  Mar 2 
M  Recitation 6 Problems  Solutions 

Mar 3 
T  15 (A)  Algebraic Structures [ PPT  PDF ]  
Mar 5 
R  16 (A)  Polynomials and Error Correction [ PPT  PDF ] Quiz 4 
Hwk8  Handout1  Handout2  Solutions to Warmup  Hwk7 Sols  
SPRING BREAK  
9  Mar 16 
M  Recitation 7 Problems  Solutions 

Mar 17 
T  17 (L)  Graphs I [ PPT  PDF ]  
Mar 19 
R  18 (L)  Graphs II [ PPT  PDF ] 
Hwk9  Solutions to Warmup  Hwk8 Sols  
10  Mar 23 
M  Recitation 8: TEST 2
[ Practice Test A 
Solutions ]
[ Practice Test B  Solutions ] 

Mar 24 
T  19 (D)  Finite Automata [ PPT  PDF ] 

Mar 26 
R  20 (B)  Social Networks [ PDF ] 

11  Mar 30 
M  Recitation 9 Problems  Solutions 

Mar 31 
T  21 (A)  This is the BigOh!
[ PPT  PDF ]
Quiz 5 
Hwk10  Hwk9 Sols  
Apr 2 
R  22 (A)  Grade School Revisited: How to Add and Multiply [ PPT  PDF ]  
12  Apr 6 
M  Recitation 10
Problems  Solutions 

Apr 7 
T  23 (A)  Cantor's Legacy: Infinity and Diagonalization [ PPT  PDF ]  Hwk11  Solutions to Warmup  Hwk10 Sols  
Apr 9 
R  24 (L)  Turing's Legacy: The Limits of Computation [ PPT  PDF ] 

13  Apr 13 
M  Recitation 11: TEST 3 [ Practice Test  Solutions ] 

Apr 14 
T  25 (A)  Godel's Legacy: What is a Proof? [ PPT  PDF ]  
Apr 16 
R  No Class: Carnival  
14  Apr 20 
M  Recitation 12 Problems  Solutions 

Apr 21 
T  26 (L) 
Efficient Reductions Between Problems [ PPT  PDF ] 
Hwk12  Solutions to Warmup  Hwk11 Sols  
Apr 23 
R  27 (L)  Complexity Theory: What is the PversusNP Question?
[ PPT
 PDF ]
Quiz 6 

15  Apr 27 
M  Recitation 13 Problems  Solutions 

Apr 28 
T  28 (A)  Combating Intractability [ PPT  PDF ]  
Apr 30 
R  29  Epilogue  Hwk12 Sols  
FINAL EXAM: Tuesday May 5, 8:3011:30. Location DH 2210 and 2315. [Practice Final 1  Practice Final 2 (Solutions)] 