
Week  Date  Day  Lecture  Topic  Available  Due 
1  Aug 24 
M  No Recitations  
Aug 25 
T  1 (A) 
Pancakes with a Problem [ PPT  PDF ]  Syllabus Cheating policy 

Aug 27 
R  2 (A) 
Inductive Reasoning [ PPT  PDF ]  Hwk1  Warmup  Solutions


2  Aug 31 
M  Recitation 1  Solutions  
Sep 1 
T  3 (A) 
Games: Which Player Wins? [ PPT  PDF ]  
Sep 3 
R  4 (A) 
Solving Problems, Writing Proofs and Enjoying the Pain: How to Succeed in 251
[ PPT 
PDF ]
Quiz 1 
Hwk2  Warmup  Solutions  Hwk1  
3  Sep 7 
M  No Recitations: Labor Day  
Sep 8 
T  5 (A) 
Ancient Wisdom: Choose Your Representation, Unary and Binary [ PPT  PDF ]  
Sep 10 
R  6 (J) 
Counting I: Choice Trees and Correspondences [ PPT  PDF ] 
Hwk3  Warmup  Solutions  Hwk2  
4  Sep 14 
M  Recitation 2  Solutions  
Sep 15 
T  7 (J) 
Counting II: Pascal, Binomials and Other Tricks [ PPT  PDF ] 

Sep 17 
R  8 (J) 
Counting III: Generating Functions
[ PPT 
PDF ]
Quiz 2 
Hwk4  Warmup  Solutions  Hwk3  
5  Sep 21 
M  Recitation 3  Solutions  
Sep 22 
T  9 
No Lecture!  
Sep 24 
R  10 (A) 
Fibonacci, Recurrences, and
Continued Fractions [ PPT  PDF ] 
Hwk5  Warmups 
Solutions Practice Test(for HW) 
Hwk4  
6  Sep 28 
M  Recitation 4:
TEST 1 [ Solutions ]
Practice Test(Not for HW)  Solutions 

Sep 29 
T  11 (A) 
Probability I: Sample Spaces and Expectations [ PPT  PDF ]  
Oct 1 
R  12 (A) 
Probability II: Infinite Sample Spaces and Random Walks [ PPT  PDF ] 
Hwk6  Warmups 
Solutions 
Hwk5  
7  Oct 5 
M  Recitation 5  Solutions  
Oct 6 
T  13 (A) 
The Math of 1950's Dating [ PPT  PDF ] Quiz 3 

Oct 8 
R  14 (A) 
Number Theory [ PPT  PDF ]  Hwk7  Warmup 
Solutions 
Hwk6  
8  Oct 12 
M  Recitation 6  Solutions  
Oct 13 
T  15 (J) 
Cryptography and RSA [ PPT  PDF ]  
Oct 15 
R  16 (J) 
Algebraic Structures: Groups, Rings and Fields [ PPT  PDF ] 
Hwk8  Warmup 
Solutions 
Hwk7  
9  Oct 19 
M  Recitation 7  Solutions  
Oct 20 
T  17 (J) 
Randomized Primality Testing [ PPT  PDF ] Quiz 4 

Oct 22 
R  18 (J) 
Graphs I: Trees and Planar Graphs [ PPT  PDF ] 
Hwk9  Warmup  Solutions  Hwk8  
10  Oct 26 
M  Recitation 8: TEST 2 [ Solutions ] Practice Test  Solutions 

Oct 27 
T  19 (J) 
Graphs II: Matchings, Tours and Other Graph Theory [ PPT  PDF ] 

Oct 29 
R  20 (A) 
Finite Automata and Languages [ PPT  PDF ] 

11  Nov 2 
M  Recitation 9  Solutions  
Nov 3 
T  21 (A) 
This is the BigOh!
[ PPT 
PDF ] Quiz 5 
Hwk10  Warmup  Solutions  Hwk9  
Nov 5 
R  22 (A) 
Grade School Revisited: How to Add and Multiply [ PPT  PDF ]  
12  Nov 9 
M  Recitation 10  Solutions  
Nov 10 
T  23 (A) 
Polynomials and Coding [ PPT  PDF ]  Hwk11  Warmup  Solutions  Hwk10 

Nov 12 
R  24 (J) 
Cantor's Legacy: Infinity And Diagonalization [ PPT  PDF ]  
13  Nov 16 
M  Recitation 11: TEST 3 Practice Test  Solutions 

Nov 17 
T  25 (J) 
Turing's Legacy: The Limits of Computation [ PPT  PDF ]  
Nov 19 
R  26 (J) 
Godel's Legacy: What is a Proof? [ PPT  PDF ] Quiz 6 

14  Nov 23 
M  Recitation 12  Solutions  
Nov 24 
T  27 (J) 
Efficient Reductions Between Problems [ PPT  PDF ] 
Hwk12  Warmup  Hwk11  
Nov 26 
R  No Class: Thanksgiving Break  
15  Nov 30 
M  Recitation 13  Solutions  
Dec 1 
T  28 (J) 
Complexity Theory: what is the PversusNP Question? [ PPT  PDF ]  
Dec 3 
R  29 (A/J) 
Epilogue [ PPT  PDF ]  Hwk12  
FINAL EXAM: Dec 15, 8:30A11:30A GHC 4401 Practice Final  Solutions 