
Week  Date  Day  Lecture  Topic  Available  Due 
1  Aug 25 
M  No Recitations  
Aug 26 
T  1 (A) 
Pancakes with a Problem [slides  printable  video]  Syllabus Cheating policy 

Aug 28 
R  2 (A) 
Inductive Reasoning [slides  printable  video]  Hwk1 
Solutions 

2  Sep 1 
M  LABOR DAY: No Recitations  
Sep 2 
T  3 (A) 
Games: Which Player Wins? [slides  printable  video] 

Sep 4 
R  4 (A) 
Solving Problems, Writing Proofs and Enjoying the Pain: How to Succeed in 251
Quiz 1 [slides  printable  video] 
Hwk2 
Solutions  Solutions to Warmup 
Hwk1  
3  Sep 8 
M  Recitation 1  Solutions  
Sep 9 
T  5 (A) 
Ancient Wisdom: Choose Your Representation, Unary and Binary [slides  printable  video video2] 

Sep 11 
R  6 (J) 
Counting I: Choice Trees and Correspondences [slides  printable  video] 
Hwk3  Solutions  Solutions to Warmup 
Hwk2  
4  Sep 15 
M  Recitation 2  Solutions  Induction pitfalls  
Sep 16 
T  7 (J) 
Counting II: Pirates and Binomials [slides  printable  video] 

Sep 18 
R  8 (J) 
Counting III: Pascal and Generating Functions
[slides 
printable 
handout 
video]
Quiz 2 
Hwk4
 Solutions  Solutions to Warmup 
Hwk3  
5  Sep 22 
M  Recitation 3 Solutions  
Sep 23 
T  9 (J) 
Fibonacci, Recurrences, and Continued Fractions [slides  printable  handout  video]  
Sep 25 
R  10 (J) 
Probability I: Sample Spaces and Expectations [slides  printable  handout  video]  Hwk5  Solutions  Solutions to Warmup  Hwk4  
6  Sep 29 
M  Recitation 4: TEST 1
[Practice Test  Solutions] 

Sep 30 
T  11 (J) 
Probability II: Infinite Sample Spaces and Random Walks [slides  printable  handout  video ] 

Oct 2 
R  12 (A) 
The Math of 1950's Dating [slides  printable  video ] 
Hwk6  Solutions Solutions to Warmup 
Hwk5  
7  Oct 6 
M  Recitation 5  Solutions  
Oct 7 
T  13 (A) 
Number Theory [slides  printable  video ] Quiz 3 

Oct 9 
R  14 (A) 
Cryptography and RSA [slides  printable  video] 
Hwk7 Solutions  Solutions to Warmup 
Hwk6  
8  Oct 13 
M  Recitation 6  Solutions  
Oct 14 
T  15 (A) 
Algebraic Structures: Groups, Rings and Fields [slides  printable  video ] 

Oct 16 
R  16 (A) 
Randomized Primality Testing [slides  handout  video ] 
Hwk8  Solutions  Hwk7  
9  Oct 20 
M  Recitation 7  Solutions  
Oct 21 
T  17 (A) 
Auctions, Voting and Social Choice [slides  handout  video ] Quiz 4 

Oct 23 
R  18 (J) 
Graphs I: Trees and Planar Graphs [slides  printable  video ] 
Hwk9  Solutions  Hwk8  
10  Oct 27 
M  Recitation 8: TEST 2
Practice Test 2 (Solutions) 

Oct 28 
T  19 (J) 
Graphs II: Matchings, Tours and Other Graph Theory [slides  printable  video] 

Oct 30 
R  20 (J) 
Finite Automata [slides  printable  video] 

11  Nov 3 
M  Recitation 9  Solutions  
Nov 4 
T  21 (J) 
This is the BigOh! [slides  printable  video] Quiz 5 
Hwk10  Solutions to Warmup Solutions  Hwk9  
Nov 6 
R  22 (J) 
Grade School Revisited: How to Add and Multiply [slides  printable  video]  
12  Nov 10 
M  Recitation 10  Solutions  
Nov 11 
T  23 (A) 
Parallel Computation [slides  handout  video ]  Hwk11  Solutions to Warmup Solutions  Hwk10 

Nov 13 
R  24 (A) 
Cantor's Legacy: Infinity And Diagonalization [slides  handout  video1  video2 ]  
13  Nov 17 
M  Recitation 11: TEST 3
[Practice Test 3  Solutions] 

Nov 18 
T  25 (A) 
Turing's Legacy: The Limits of Computation [slides  handout  video  also L24video2 ]  
Nov 20 
R  26 (J) 
Godel's Legacy: What is a Proof? [slides  handout  also L25video ] Quiz 6 
Hwk12  Solutions  
14  Nov 24 
M  Recitation 12 Solutions  
Nov 25 
T  27 (J) 
Efficient Reductions Between Problems [slides  printable  handout 1  handout 2  video] 
Hwk11  
Nov 27 
R  No Class: Thanksgiving Break  
15  Dec 1 
M  Recitation 13  Solutions  
Dec 2 
T  28 (J) 
Complexity Theory: what is the PversusNP Question? [slides  printable  video]  
Dec 4 
R  29  Epilogue  Hwk12  
FINAL EXAM: Tuesday Dec 9, 5:308:30pm Wean 7500 [Practice Final  Partial Solutions ] 