-
Week 1 (Jan 13): Introduction, basic definitions, randomized quicksort, AND-OR tree, Karger's mincut algorithm.
-
Week 2 (Jan 21): Random variables, expectation, analysis of randomized quicksort.
-
Week 3 (Jan 28): Markov's inequality, Count-Min sketch, Chebyshev's inequality, randomized median finding, count sketch.
-
Week 4 (Feb 4): Lower bounds, Yao minimax principle, Chernoff/Hoeffding bounds.
-
Week 5 (Feb 11): Discrepancy, packet routing, randomized rounding.
-
Week 6 (Feb 18): Universal hashing, cuckoo hashing.
-
Week 7 (March 3): Midterm 1
-
Week 8 (March 10): Markov chains, randomized algorithm for 2-SAT.
-
Week 9 (March 17): Random walks on undirected graphs, Markov chain Monte Carlo.
-
Week 10 (March 24): Coupling, generating random spanning trees, generating random colorings, approximate counting.
-
Week 11 (March 31): Martingales, stopping times, Doob martingales, Azuma's inequality, stochastic bin packing.
-
Week 12 (April 7): Online algorithms, online bipartite matching, k-server problem.
-
Week 13 (April 14): Midterm 2.