
Week  Date  Day  Lecture  Topic  Available  Due 
1  Aug 28 
M  Recitation 1  
Aug 29 
T  1  Pancakes with a Problem [PPT, PDF, video] 
Hwk1
[Tex source, Stylefile] 

Aug 31 
R  2  Induction I: One Step at a Time [PPT, PDF, video]  
2  Sep 4 
M  Labor Day, no Recitation 2  
Sep 5 
T  3  Induction II: Inductive Pictures [PPT, PDF, video] 
Hwk2
[Tex source, Stylefile] 
Hwk1 Solutions  
Sep 7 
R  4 Quiz 1 
Ancient Wisdom: Unary and Binary
[PPT,
PDF,
video] Quiz1 [soln] 

3  Sep 11 
M  Recitation 3 [PDF]  
Sep 12 
T  5  Ancient Wisdom: On Raising a Number to a power [PPT, PDF, video] 
Hwk3
[Tex source, Stylefile] 
Hwk2 Solutions  
Sep 14 
R  6  Counting I: Correspondences and Choice Trees [PPT, PDF, video]  
4  Sep 18 
M  Recitation 4 [PDF]  
Sep 19 
T  7  Counting II [PPT, PDF, video] 
Hwk4
[Tex source, Stylefile] 
Hwk3 Solutions  
Sep 21 
R  8 Quiz 2 
Counting III
[PPT,
PDF,
video] Quiz2 [soln] 

5  Sep 25 
M  Recitation 5: TEST 1 [solns]  
Sep 26 
T  9  Probability I: Counting in Terms of Proportions [PPT, PDF, video] 
Hwk5
[Tex source, Stylefile] 
Hwk4 Solutions  
Sep 28 
R  10  Probability II: Random Variables and Great Expectations [PPT, PDF, video]  
6  Oct 2 
M  Recitation 6 [PDF]  
Oct 3 
T  11  Probability III: Probabilistic Method and Random Walks [PPT, PDF, video] 
Hwk6
[Tex source, Stylefile] 
Hwk5 Solutions  
Oct 5 
R  12 Quiz 3 
Ancient Wisdom: Primes, GCD, and Continued Fractions
[PPT,
PDF,
video] Quiz3 [soln] 

7  Oct 9 
M  Recitation 7 [PDF, solns]  
Oct 10 
T  13  The Golden Ratio, Fibonacci, and Other Recurrences
[PPT,
PDF,
video] 
Hwk7
[Tex source, Stylefile] 
Hwk6 Solutions  
Oct 12 
R  14  Number Theory: Number Theory and RSA
[PPT,
PDF,
video] 

8  Oct 16 
M  Recitation 8 [PDF, solns]  
Oct 17 
T  15  Algebraic Structures: Groups, Rings and Fields
[PPT,
PDF,
video] 
Hwk8 clarified
[Tex source, Stylefile, numbers.txt] 
Hwk7 Solutions  
Oct 19 
R  16 Quiz 4 
Polynomials, Secret Sharing and Error Correction
[PPT,
PDF,
video] [Quiz4 soln] 

9  Oct 23 
M  Recitation 9 [PDF, solns]  
Oct 24 
T  17  Randomized Primality and Fingerprinting
[PPT,
PDF,
video] 
Hwk9
[Tex source, Circuit Drawing] 
Hwk8 Solutions  
Oct 26 
R  18  1950's Dating: Who Wins the Battle of the Sexes? [PPT, PDF, video]  
10  Oct 30 
M  Recitation 10: TEST 2 [solns]  
Oct 31 
T  19  Problem Solving: Where Does the Aha Come From? [PPT, PDF, video]  Hwk9 Continues  
Nov 2 
R  20  Graphs I [PPT, PDF, Proofs, video]  
11  Nov 6 
M  Recitation 11 [PDF, solns]  
Nov 7 
T  21  Graphs II [PPT, PDF] video] 
Hwk10
[Tex source] 
Hwk9 Solutions  
Nov 9 
R  22 Quiz 5 
Finite Automata
[PPT,
PDF,
video]
[Quiz5 soln] 

12  Nov 13 
M  Recitation 12 [PDF, solns]  
Nov 14 
T  23  On Time Versus Input Size. aka the BigOh [PPT, PDF, video] 
Hwk11
[Tex source] 
Hwk10 Solutions  
Nov 16 
R  24  Grade School Revisited: How to Add and Multiply [PPT, PDF, video]  
13  Nov 20 
M  Recitation 13: TEST 3 [solns]  
Nov 21 
T  25  Cantor's Legacy: Infinity And Diagonalization [PPT, PDF, video] 
Hwk12 clarified
[Tex Source] Ken Thompson article 
Hwk11 Solutions  
Nov 23 
R  No Class: Thanksgiving  
14  Nov 27 
M  Recitation 14 [PDF, solns]  
Nov 28 
T  26  Turing's Legacy: The Limits of Computation [PPT, PDF, video]  Hwk12 Continues  
Nov 30 
R  27 Quiz 6 
Thales' and Godel's Legacy: What is a Proof?
[PPT,
PDF,
video]
[Quiz6 soln] 

15  Dec 4 
M  Recitation 15 [PDF, solns]  
Dec 5 
T  28  Reductions: A Graph called Gadget [PPT, PDF, video]  Hwk12 Solutions  
Dec 7 
R  29  Complexity: What is the PversusNP Question? [PPT, PDF, video]  
F  Dec 18 
M  Final: 5:30P  8:30P, Wean 7500 