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.