 |
|
| Week | Date | Day | Lecture | Topic | Available | Due |
| 1 | Aug 26 |
M | Recitation 1 (Latex) | |||
| Aug 27 |
T | 1 (VA) | Pancakes with a Problem
Lecture slides [PPT, PDF] Notes on Pancakes |
|||
| Aug 29 |
R | 2 (VA) | Inductive Reasoning: One Step at a Time
Lecture slides [PPT, PDF] Notes on Induction: 1, 2, 3. Notes on common induction mistakes |
Hwk1 | ||
| 2 | Sep 2 |
M | NO CLASSES | |||
| Sep 3 |
T | 3 (VA) | Proofs
Lecture slides [PPT, PDF] Notes on proof methods Quiz 1 |
|||
| Sep 5 |
R | 4 (AP) | Counting-I
Lecture slides [PDF] Notes on Counting |
Hwk2 | Hwk1 | |
| 3 | Sep 09 |
M | Recitation 2 (Counting I) | |||
| Sep 10 |
T | 5 (AP) | Counting II
Lecture slides [PDF] Quiz 2 |
|||
| Sep 12 |
R | 6 (AP) | Probability- I
Lecture slides [PDF] Notes on probability |
Hwk3 | Hwk2 | |
| 4 | Sep 16 |
M | Recitation 3 (Counting) | |||
| Sep 17 |
T | 7 (AP) | Probability- II Lecture slides [PDF] Notes on random variables Quiz 3 |
|||
| Sep 19 |
R | 8 (VA) | Graphs-I
[PPT,
PDF]
Notes on Graphs I |
Hwk4 |
Hwk3 | |
| 5 | Sep 23 |
M | Recitation 4 (Probability) | |||
| Sep 25 |
T | 9 (VA) | Graphs-II
[PPT,
PDF
]
Quiz 4 |
|||
| Sep 26 |
R | 10 (VA) | Graphs-III
[PPT,
PDF
Notes on Graphs II] |
Hwk4 | ||
| 6 | Sep 30 |
M | Recitation 5 (midterm) | |||
| Oct 01 |
T | TEST 1
Practice Test [Solutions] Midterm 1 [Solutions] |
||||
| Oct 03 |
R | 11 (AP) | Time Complexity Lecture slides [PDF] |
Hwk5 | ||
| 7 | Oct 07 |
M | Recitation 6 | |||
| Oct 08 |
T | 12 (AP) |
Cake cutting
Lecture slides [PDF] Notes on cake cutting Fun reading on cake cutting Quiz 5 |
|||
| Oct 10 |
R | 13 (AP) | Reductions Lecture slides [PDF] 451 Notes |
Hwk6 | Hwk5 | |
| 8 | Oct 14 |
M | Recitation 7: Reductions | |||
| Oct 15 | T | 14 (AP) | P vs. NP Lecture slides [PDF] 451 Notes Quiz 6 |
|||
| Oct 17 |
R | 15 (AP) | Computational social choice Lecture slides [PDF] Fun reading on computational social choice |
Hwk7 | Hwk6 | |
| 9 | Oct 21 |
M | Recitation 8 NP | |||
| Oct 22 |
T | 16 (AP) | Approximation algorithms Lecture slides [PDF] Quiz 7 |
|||
| Oct 24 |
R | 17 (AP) | Online algorithms Lecture slides [PDF] Notes on online algorithms |
Hwk8 | Hwk7 | |
| 10 | Oct 28 |
M | Recitation 9 (Voting and Approximation) | |||
| Oct 29 |
T | 18 (AP) | Interactive proofs Lecture slides [PDF] Notes on interactive proofs Quiz 8 |
|||
| Oct 31 |
R | 19 (AP) |
Learning theory Lecture slides [PDF] Notes on learning theory (ch. 7+8) |
Hwk8 | ||
| 11 | Nov 04 |
M | Recitation 10 | |||
| Nov 05 |
T | TEST 2
Practice Test 2 [Solutions] Midterm 2 [Solutions] |
||||
| Nov 07 |
R | 20 (VA) |
Cantor's Legacy: Infinity And Diagonalization Lecture slides [PDF] |
Hwk9 | ||
| 12 | Nov 11 |
M | Recitation 11 | |||
| Nov 12 |
T | 21 (VA) |
Finite State Automata Lecture slides [PDF] Quiz 9 |
|||
| Nov 14 |
R | 22 (VA) | Turing and Church's Legacy: The Limits of Computation [PDF] | Hw10 | Hwk9 | |
| 13 | Nov 18 |
M | Recitation 12 | |||
| Nov 19 |
T | 23 (VA) | Number theory Lecture slides [PDF] Notes on Number theory Quiz 10 |
|||
| Nov 21 |
R | 24 (VA) | RSA Lecture slides [PDF] |
|||
| 14 | Nov 25 |
M | Recitation 13 | |||
| Nov 26 |
T | 25 (VA) | Group Theory Lecture slides [PDF] Notes on group theory |
Hw11 | Hwk10 | |
| Nov 28 |
R | No Classes | ||||
| 15 | Dec 02 |
M | Recitation 14 | |||
| Dec 03 |
T | 26 (VA) | Fields, Polynomials Lecture notes [PDF] Notes on polynomials, error correction Quiz 11 |
|||
| Dec 05 |
R | 27 (VA) | Random Walks Lecture slides [PDF] |
Hwk11 | ||
| Dec 10 |
T | Final Exam
Practice Test Solutions [Quizzes] |
8:30am - 11:30am | PH 100 | ||