 |
|
| 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 Big-Oh [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 P-versus-NP Question? [PPT, PDF, video] | |||
| F | Dec 18 |
M | Final: 5:30P - 8:30P, Wean 7500 | |||