 |
|
| Week | Date | Day | Lecture | Topic | Available | Due |
| 1 | Jan 12 |
M | No Recitations | |||
| Jan 13 |
T | 1 (L) | Solving Problems, Writing Proofs and Enjoying the Pain: How to Succeed in 251 [ PPT | PDF ] | Hwk1 | Individual Part | ||
| Jan 15 |
R | 2 (L) | Pancakes with a Problem [ PPT | PDF ] |
|||
| 2 | Jan 19 |
M | MLK DAY: No Recitations | |||
| Jan 20 |
T | 3 (L) | Inductive Reasoning
[ PPT | PDF ] Induction Dos and Don'ts |
Hwk2 | Solutions to Warmup | Hwk1 Sols | |
| Jan 22 |
R | 4 (L) |
Games: Which Player Wins?
[ PPT | PDF ]
Quiz 1 |
|||
| 3 | Jan 26 |
M | Recitation 1 Problems | Solutions |
|||
| Jan 27 |
T | 5 (A) | Ancient Wisdom: Choose your Representation, Unary and Binary [ PPT | PDF ] |
Hwk3 | Solutions to Warmup | Hwk2 Sols | |
| Jan 29 |
R | 6 (A) | Counting I: Choice Trees and Correspondences [ PPT | PDF ] |
|||
| 4 | Feb 2 |
M | Recitation 2 Problems | Solutions |
|||
| Feb 3 |
T | 7 (A) | Counting II: Pigeons, Pirates and Pascal [ PPT | PDF ] |
Hwk4 | Solutions to Warmup | Hwk3 Sols | |
| Feb 5 |
R | 8 (A) | Counting III: Generating Functions Quiz 2 [ PPT | PDF ] GF Handouts from Fall 08 [1], [2] |
|||
| 5 | Feb 9 |
M | Recitation 3 Problems | Solutions |
|||
| Feb 10 |
T | 9 (L) | Primes, GCD, and Continued Fractions [ PPT | PDF ] |
Hwk5 | Practice Test | Solutions to Warmup | Hwk4 Sols | |
| Feb 12 |
R | 10 (L) | The Math of the 1950's Dating [ PPT | PDF ] |
|||
| 6 | Feb 16 |
M | Recitation 4: TEST 1
[Practice Test Solutions]
[Additional Practice Test (NOT part of assignment 5) | Solutions] |
|||
| Feb 17 |
T | 11 (L) | Probability I [ PPT | PDF ] |
|||
| Feb 19 |
R | 12 (L) | Probability II [ PPT | PDF ] |
Hwk6 | Solutions to Warmup | Hwk5 Sols | |
| 7 | Feb 23 |
M |
Recitation 5 Problems | Solutions |
|||
| Feb 24 |
T | 13 (A) | Number Theory [ PPT | PDF ] Quiz 3 |
|||
| Feb 26 |
R | 14 (A) | Cryptography and RSA [ PPT | PDF ] | Hwk7 | Solutions to Warmup | Hwk6 Sols | |
| 8 | Mar 2 |
M | Recitation 6 Problems | Solutions |
|||
| Mar 3 |
T | 15 (A) | Algebraic Structures [ PPT | PDF ] | |||
| Mar 5 |
R | 16 (A) | Polynomials and Error Correction [ PPT | PDF ] Quiz 4 |
Hwk8 | Handout1 | Handout2 | Solutions to Warmup | Hwk7 Sols | |
| SPRING BREAK | ||||||
| 9 | Mar 16 |
M | Recitation 7 Problems | Solutions |
|||
| Mar 17 |
T | 17 (L) | Graphs I [ PPT | PDF ] | |||
| Mar 19 |
R | 18 (L) | Graphs II [ PPT | PDF ] |
Hwk9 | Solutions to Warmup | Hwk8 Sols | |
| 10 | Mar 23 |
M | Recitation 8: TEST 2
[ Practice Test A |
Solutions ]
[ Practice Test B | Solutions ] |
|||
| Mar 24 |
T | 19 (D) | Finite Automata [ PPT | PDF ] |
|||
| Mar 26 |
R | 20 (B) | Social Networks [ PDF ] |
|||
| 11 | Mar 30 |
M | Recitation 9 Problems | Solutions |
|||
| Mar 31 |
T | 21 (A) | This is the Big-Oh!
[ PPT | PDF ]
Quiz 5 |
Hwk10 | Hwk9 Sols | |
| Apr 2 |
R | 22 (A) | Grade School Revisited: How to Add and Multiply [ PPT | PDF ] | |||
| 12 | Apr 6 |
M | Recitation 10
Problems | Solutions |
|||
| Apr 7 |
T | 23 (A) | Cantor's Legacy: Infinity and Diagonalization [ PPT | PDF ] | Hwk11 | Solutions to Warmup | Hwk10 Sols | |
| Apr 9 |
R | 24 (L) | Turing's Legacy: The Limits of Computation [ PPT | PDF ] |
|||
| 13 | Apr 13 |
M | Recitation 11: TEST 3 [ Practice Test | Solutions ] |
|||
| Apr 14 |
T | 25 (A) | Godel's Legacy: What is a Proof? [ PPT | PDF ] | |||
| Apr 16 |
R | No Class: Carnival | ||||
| 14 | Apr 20 |
M | Recitation 12 Problems | Solutions |
|||
| Apr 21 |
T | 26 (L) |
Efficient Reductions Between Problems [ PPT | PDF ] |
Hwk12 | Solutions to Warmup | Hwk11 Sols | |
| Apr 23 |
R | 27 (L) | Complexity Theory: What is the P-versus-NP Question?
[ PPT
| PDF ]
Quiz 6 |
|||
| 15 | Apr 27 |
M | Recitation 13 Problems | Solutions |
|||
| Apr 28 |
T | 28 (A) | Combating Intractability [ PPT | PDF ] | |||
| Apr 30 |
R | 29 | Epilogue | Hwk12 Sols | ||
| FINAL EXAM: Tuesday May 5, 8:30-11:30. Location DH 2210 and 2315. [Practice Final 1 | Practice Final 2 (Solutions)] |
||||||