Approximate schedule (subject to change):
Unless stated otherwise (in class), every assignment covers the material taught from the beginning of the course to the day it is released.
| 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 | Mini-intro to random walks | More about entropy and about random walks |
| 13 | Complementary material | Complementary material |
Tentative homework schedule (this may change so watch the HW section):
| Assignment | Release date | Due date |
|---|---|---|
| 1 | 1.11 | 26.11 |
| 2 | 29.11 | 31.12 |
| 3 | 3.1 | 28.1 |
| 4 | 28.1 | 11.3 |