[Jun 10] Assignment 6 is out, due on June 22. [May 20] Assignment 5 is out, due on June 1. [Apr 30] Assignment 4 is out, due on May 18. [Apr 14] Assignment 3 is out, due on Apr. 27. [Mar 24] Assignment 2 is out, due on Apr. 13. [Mar 09] Assignment 1 is out, due on Mar. 23.
Lecture Notes
[Jun 15][notes][slides][handout] Canonical paths, Sampling matchings [Jun 08][notes][slides][handout] Sampling Proper Colorings, Edge Expansion, Cheeger's Inequality [Jun 01][notes][slides][handout] Coupling, Mixing Time, Relaxation Time [May 25][notes][slides][handout] Fundamental Theorem of Markov Chains, Spectral Decomposition Theorem [May 18][notes][slides][handout] Partial Rejection Sampling for Independent Sets [May 11][notes][slides][handout] Sampling, Rejection sampling, Counting DNF [Apr 28][notes][slides][handout] Moser-Tardos' witness tree proof of Lovász local lemma [Apr 27][notes][slides][handout] Lovász local lemma [Apr 20][notes][slides][handout] The Probabilistic Method, Max Cut, Max Sat, Linear Programming Relaxation [Apr 13][notes][slides][handout] Optional Stopping Theorem [Mar 30][notes][slides][handout] Martingale, Azuma-Hoeffding, Doob's Martingale [Mar 23][notes][slides][handout] Chernoff Bound, Hoeffding Inequality, Multi-Armed Bandits, UCB [Mar 16][notes][slides][handout] Balls-into-Bins, Markov Inequality, Chebyshev's Inequality [Mar 09][notes][slides][handout] Linearity of Expectation, Coupon Collector, Karp-Upfal-Wigderson Inequality [Mar 02][notes][slides][handout] Polynomial Identity Testing, Schwartz-Zippel Theorem, Karger's Min-cut Algorithm