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