 |
|
| 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 Big-Oh! [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 L24-video2 ] | |||
| Nov 20 |
R | 26 (J) |
Godel's Legacy: What is a Proof? [slides | handout | also L25-video ] 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 P-versus-NP Question? [slides | printable | video] | |||
| Dec 4 |
R | 29 | Epilogue | Hwk12 | ||
| FINAL EXAM: Tuesday Dec 9, 5:30-8:30pm Wean 7500 [Practice Final | Partial Solutions ] |
||||||