 |
|
| Week | Date | Day | Lecture | Topic | Available | Due |
| 1 | Aug 23 |
M | Recitation 1; A LaTeX Tutorial Recitation 1 LaTeX Solutions |
Syllabus Cheating policy |
||
| Aug 24 |
T | 1 (A) |
Pancakes with a Problem [ PPT | PDF ] |
Hwk1 |
Warmups |
Solutions |
||
| Aug 26 |
R | 2 (A) |
Inductive Reasoning [ PPT | PDF ] | |||
| 2 | Aug 30 |
M | Recitation 2 Recitation 2 Solutions | |||
| Aug 31 |
T | 3 (A) |
Ancient Wisdom: Choose Your Representation, Unary and Binary [ PPT | PDF ] |
|||
| Sep 2 |
R | 4 (A) |
Solving Problems, Writing Proofs, and Enjoying the Pain: How to Succeed in 251 [ PPT | PDF ] Quiz 1 Solutions |
Hwk1 | ||
| 3 | Sep 6 |
M | No Recitations! | |||
| Sep 7 |
T | 5 (D) |
Games I: Which Player Wins? [ PPT | PDF ] |
Hwk2 |
Warmups |
Solutions
|
||
| Sep 9 |
R | 6 (D) |
Games II: Nimbers [ PPT | PDF ] Quiz 2 Solutions |
|||
| 4 | Sep 13 |
M | Recitation 3 Recitation 3 Solutions | |||
| Sep 14 |
T | 7 (D) |
Counting I: Choice Trees and Correspondences [ PPT | PDF ] |
|||
| Sep 16 |
R | 8 (D) |
Counting II: Pascal,
Binomials, and Other Tricks [ PPT | PDF ] Quiz 3 Solutions |
Hwk3 |
Warmups |
Solutions
|
Hwk2 | |
| 5 | Sep 20 |
M | Recitation 4 Recitation 4 Solutions | |||
| Sep 21 |
T | 9 (AB) |
Counting III: Generating Functions [ PPTX | PDF ] |
|||
| Sep 23 |
R | 10 (A) |
Propositional Logic
[ PPT | PDF ]
Quiz 4 Solutions |
Hwk3 (Due Friday) | ||
| 6 | Sep 27 |
M | Recitation 5: TEST 1| Practice Test | Solutions | |||
| Sep 28 |
T | 11 (A) |
Probability I: Basic Probability [ PPT | PDF ] |
Hwk4 |
Warmups |
Solutions
|
||
| Sep 30 |
R | 12 (A) |
Probability II: Great Expectations
[ PPT | PDF ]
Quiz 5 Solutions |
|||
| 7 | Oct 4 |
M | Recitation 6 Recitation 6 Solutions | |||
| Oct 5 |
T | 13 (D) |
Number Theory [ PPT | PDF ] | |||
| Oct 7 |
R | 14 (D) |
Cryptography and RSA
[ PPTX | PDF ] Code: number.ml big_number.ml Quiz 6 Solutions |
Hwk5 |
Warmups |
Solutions
|
Hwk4 | |
| 8 | Oct 11 |
M | Recitation 7 Recitation 7 Solutions | |||
| Oct 12 |
T | 15 (A) |
Algebraic Structures: Groups, Rings, and Fields [ PPT | PDF ] | |||
| Oct 14 |
R | 16 (A) |
Error Correction Codes
[ PPT | PDF ]
Quiz 7 Solutions |
|||
| 10 | Oct 18 |
M | Recitation 8 Recitation 8 Solutions | |||
| Oct 19 |
T | 17 (A) |
Probability III: Infinite Sample Spaces and Random Walks (plus Lagrange) [ PPT | PDF ] | |||
| Oct 21 |
R | 18 (D) |
Graphs I:
Trees and Planar Graphs
[ PPT | PDF ]
Quiz 8 Solutions |
Hwk6 | Warmups | Solutions | Hwk5 | |
| 11 | Oct 25 |
M | Recitation 9: TEST 2| Practice Test | Solutions | |||
| Oct 26 |
T | 19 (D) |
Graphs II: Matchings, Tours, and Other Graph Theory [ PPT | PDF ] | |||
| Oct 28 |
R | 20 (D) |
Finite Automata and Languages
[ PPT | PDF ]
Quiz 9 Solutions |
|||
| 12 | Nov 1 |
M | Recitation 10 Recitation 10 Solutions | |||
| Nov 2 |
T | 21 (D) |
The Stable Marriage Problem [ Book Excerpt, Lecture Notes ] | Hwk7 | Helpful Reading | Hwk6 | |
| Nov 4 |
R | 22 (D) |
Algorithms: Grade School and Beyond!
[ PPT | PDF ]
Quiz 10 Solutions |
|||
| 13 | Nov 8 |
M | Recitation 11 Recitation 11 Solutions | |||
| Nov 9 |
T | 23 (A) |
Cantor's Legacy: Infinity and Diagonalization [ PPT | PDF | notes ] | |||
| Nov 11 |
R | 24 (A) |
Turing's Legacy: The Limits of Computation [ PPT | PDF ] | Hwk7 | ||
| 14 | Nov 15 |
M | Recitation 12: TEST 3| Practice Test | Solutions | |||
| Nov 16 |
T | 25 (A) |
Gödel's Legacy: What is a Proof? [ PPT | PDF ] | Hwk8 | Warmups | Solutions | ||
| Nov 18 |
T | 26 (D) |
Efficient Reductions Between Problems
[ PPT | PDF ]
Quiz 11 Solutions |
|||
| 15 | Nov 22 |
M | Recitation 13 Recitation 13 Solutions | |||
| Nov 23 |
T | 27 (D) |
Complexity Theory: What is the P vs. NP Question? [ PPT | PDF ] | Hwk9 | Warmups | Solutions | Hwk8 | |
| Nov 25 |
R | No Class: Thanksgiving Have Fun! |
||||
| 16 | Nov 29 |
M | Recitation 14 Recitation 14 Solutions | |||
| Nov 30 |
T | 28 (A) |
Approximation Algorithms
[ PPT | PDF ]
Quiz 12 Solutions |
|||
| Dec 2 |
R | 29 (D) |
Voting Schemes [ PPT | PDF ] | Hwk9 | ||
| FINAL EXAM: Tuesday Dec 14, 8:30-11:30am Location TBD Practice Final Solutions |
||||||