Lectures & Schedule
| # | Day | Date | Topic / Notes | PDF / Video |
|---|---|---|---|---|
| 1 | Wednesday | August 26, 2026 | Introduction | intro |
| 2 | Friday | August 28, 2026 | Some probability: conditional probability, independence, expectation, linearity of expectation, Markov's inequality | expectations |
| 3 | Wednesday | September 02, 2026 | Quick sort in expectations; Verification | quick_sort verify |
| 4 | Friday | September 04, 2026 | Chebychev inequality | alias_method chebychev recording youtube |
| 5 | Wednesday | September 09, 2026 | Occupancy | occupancy |
| 6 | Friday | September 11, 2026 | $k$-wise Independence | k_wise |
| 7 | Wednesday | September 16, 2026 | Hashing | hashing |
| 8 | Friday | September 18, 2026 | Closest pair; Turán's theorem; Derandomization of 3SAT via conditional expectations | closest_pair turan 3sat_derand |
| MT1 | Wednesday | September 23, 2026 | ▶ Midterm 1 (in class) — info | |
| 10 | Friday | September 25, 2026 | Discrepancy and derandomization | discrepancy |
| 11 | Wednesday | September 30, 2026 | Routing on the hypercube; Martingales | chernoff_app martingales |
| 12 | Friday | October 02, 2026 | Martingales 2 | martin_II |
| 13 | Wednesday | October 07, 2026 | Power of two choices | two_choices |
| 14 | Friday | October 09, 2026 | Power of two choices part II | |
| 15 | Wednesday | October 14, 2026 | Streaming | streaming |
| 16 | Friday | October 16, 2026 | Frequency estimation | frequency_est |
| 17 | Wednesday | October 21, 2026 | Frequency estimation 2 | freq_est_2 |
| MT2 | Friday | October 23, 2026 | ▶ Midterm 2 (in class) — info | |
| 19 | Wednesday | October 28, 2026 | Random walk II / Random walk III | rwalk_II rwalk_III |
| 20 | Friday | October 30, 2026 | Random walk III | rwalk_III |
| 21 | Wednesday | November 04, 2026 | Random walk IV | rwalk_IV |
| 22 | Friday | November 06, 2026 | Expanding graphs; Random walk V; Graph algebra | expanding_graphs rwalk_V graph_algebra |
| 23 | Wednesday | November 11, 2026 | Random walk continued | |
| 24 | Friday | November 13, 2026 | Johnson-Lindenstrauss Lemma | jl |
| 25 | Wednesday | November 18, 2026 | Entropy; Entropy II | entropy entropy_II |
| 26 | Friday | November 20, 2026 | Shannon's theorem | entropy_III |
| — | Thanksgiving Break — Give thanks, go on vacation | |||
| MT3 | Wednesday | December 02, 2026 | ▶ Midterm 3 (in class) — info | |
| 28 | Friday | December 04, 2026 | ||
| 29 | Wednesday | December 09, 2026 | Last lecture | |