Approximate schedule (subject to change):
| Week | Lecture | Recitation and Problem Solving Practice |
|---|
| 1 | Introduction | Variation distance |
| 1-2 | Linearity of expectation | Sum-Free subsets |
| 2-3 | Alterations | Two methods for derandomization |
4
| The second moment method | Applications of the second moment method |
5
| Large deviation inequalities | Large deviations in "rare" variables, multiplicative Chernoff bounds |
| 5-6 | Martingales | Additional martingale examples |
| 7-8 | The Lovász local lemma | A constructive proof of the local lemma |
| 9 | Correlation inequalities | Additional correlation inequalities
|
| 10-11 | Entropy | Shearer's inequality, applications |
| 12 | Complementary material | Complementary material |
Approximate homework schedule (schedule
will change, number
may change):
| Assignment | Release date | Due date |
|---|
| HW1 | 10/11 | 5/12 |
| HW2 | 8/12 | 2/01 |
| HW3 | 5/01 | 30/01 |
| HW4 | 2/02 | 12/04 |
