 |
|
| Week | Date | Day | Lecture | Topic | Available | Due |
| 1 | Aug 25 |
M | No Recitations | |||
| Aug 26 |
T | 1 (A) |
Pancakes with a Problem [PPT | PDF] | Syllabus Cheating policy |
||
| Aug 28 |
R | 2 (A) |
Inductive Reasoning |
Hwk1 | ||
| 2 | Sep 1 |
M | LABOR DAY: No Recitations | |||
| Sep 2 |
T | 3 (A) |
Games: Which Player Wins? | |||
| Sep 4 |
R | 4 (A) |
Solving Problems, Writing Proofs and Enjoying the Pain: How to Succeed in 251
Quiz 1 |
Hwk2 | Hwk1 | |
| 3 | Sep 8 |
M | Recitation 1 | |||
| Sep 9 |
T | 5 (A) |
Ancient Wisdom: Choose Your Representation, Unary and Binary |
|||
| Sep 11 |
R | 6 (J) |
Counting I: Choice Trees and Correspondences |
Hwk3 | Hwk2 | |
| 4 | Sep 15 |
M | Recitation 2 | |||
| Sep 16 |
T | 7 (J) |
Counting II: Pascal and Binomials | |||
| Sep 18 |
R | 8 (J) |
Counting III: Generating Functions
Quiz 2 |
Hwk4 | Hwk3 | |
| 5 | Sep 22 |
M | Recitation 3 | |||
| Sep 23 |
T | 9 (J) |
Fibonacci, Recurrences, and Continued Fractions | |||
| Sep 25 |
R | 10 (J) |
Probability I: Sample Spaces and Expectations | Hwk5 | Hwk4 | |
| 6 | Sep 29 |
M | Recitation 4: TEST 1
|
|||
| Sep 30 |
T | 11 (J) |
Probability II: Infinite Sample Spaces and Random Walks | |||
| Oct 2 |
R | 12 (A) |
The Math of the 1950's Dating | Hwk6 | Hwk5 | |
| 7 | Oct 6 |
M | Recitation 5 | |||
| Oct 7 |
T | 13 (A) |
Number Theory
Quiz 3 |
|||
| Oct 9 |
R | 14 (A) |
Cryptography and RSA | Hwk7 | Hwk6 | |
| 8 | Oct 13 |
M | Recitation 6 | |||
| Oct 14 |
T | 15 (A) |
Algebraic Structures: Groups, Rings and Fields | |||
| Oct 16 |
R | 16 (A) |
Randomized Primality Testing | Hwk8 | Hwk7 | |
| 9 | Oct 20 |
M | Recitation 7 | |||
| Oct 21 |
T | 17 (A) |
Auctions, Voting and Social Choice
Quiz 4 |
|||
| Oct 23 |
R | 18 (J) |
Graphs I: Trees and Planar Graphs |
Hwk9 | Hwk8 | |
| 10 | Oct 27 |
M | Recitation 8: TEST 2
|
|||
| Oct 28 |
T | 19 (J) |
Graphs II: Matchings, Tours and Other Graph Theory |
|||
| Oct 30 |
R | 20 (J) |
Finite Automata |
|||
| 11 | Nov 3 |
M | Recitation 9 | Hwk10 | Hwk9 | |
| Nov 4 |
T | 21 (J) |
This is the Big-Oh!
Quiz 5 |
|||
| Nov 6 |
R | 22 (J) |
Grade School Revisited: How to Add and Multiply | |||
| 12 | Nov 10 |
M | Recitation 10 | |||
| Nov 11 |
T | 23 (A) |
Other Models of Computation: Parallel, Randomized and Quantum Computation! | Hwk11 | Hwk10 |
|
| Nov 13 |
R | 24 (A) |
Cantor's Legacy: Infinity And Diagonalization | |||
| 13 | Nov 17 |
M | Recitation 11: TEST 3
|
|||
| Nov 18 |
T | 25 (A) |
Turing's Legacy: The Limits of Computation | |||
| Nov 20 |
R | 26 (J) |
Godel's Legacy: What is a Proof? Quiz 6 |
Hwk12 | Hwk11 | |
| 14 | Nov 24 |
M | Recitation 12 | |||
| Nov 25 |
T | 26 (J) |
Efficient Reductions Between Problems | |||
| Nov 27 |
R | No Class: Thanksgiving Break | ||||
| 15 | Dec 1 |
M | Recitation 13 | |||
| Dec 2 |
T | 28 (J) |
Complexity Theory: what is the P-versus-NP Question? | |||
| Dec 4 |
R | 29 | Epilogue | Hwk12 | ||