Week 1 (Jan 19th to Jan 23rd)
Verifying Polynomial Identity and Matrix Multiplication [MU 1.2-1.3] [MR 7.1-7.2]
Karger's Algorithm for Minimum Cut [MU 1.5] [MR 1.1]
Week 2 (Jan 26th to Jan 30th)
Random variables and Expectations [MU 2.1-2.4]
Coupon Collector's problem [MU 2.4.1]
Expected Running Time of Randomized Quicksort [MU 2.5]
Week 3 (Feb 2nd to Feb 6th)
Tail Inequalities: Markov, Chebyshev [MU 3.1-3.4]
Randomized Median Finding [MU 3.5]
Week 4 (Feb 9th to Feb 13th)
Chernoff Bounds: using and proving [MU 4.1-4.2]
Permutation Routing in Hypercube Networks [MU 4.6]
Week 5 (Feb 16th to Feb 20th)
Permutation Routing on Butterfly (brief discussion) [MU 4.6.2]
Complexity Theory: RP, co-RP, BPP, ZPP, and relations [MR 1.5]
Interactive Proof Systems [MR 7.7]
Week 6 (Feb 23rd to Feb 27th)
The Probabilistic Method [MU 6] [MR 5]
Approximating Max-Cut and Max-SAT using Expectation Argument [MU 6.2]
Derandomization using pairwise independent hash functions [MU 15.1.1, 15.1.2]
Derandomization using method of conditional expectations [MU 6.3] [MR 5.6]
Sample and Modify for constructing large independent sets [MU 6.4]
Introduction to Lovasz Local Lemma [MU 6.7] [MR 5.5]
Week 7 (Mar 2nd to Mar 6th)
Non-constructive proof of LLL [MU 6.7] [MR 5.5]
Beck's Algorithm for k-SAT instances satisfying LLL [MU 6.8] [MR 5.5]
Week 8 (Mar 9th to Mar 13th)
Moser-Tardos LLL algorithm and compression argument [MU 6.10]
Markov Chains/Random Walks and the 2-SAT Algorithm [MU 7.1.1]
Week 9 (Mar 16th to Mar 20th)
Week 10 (Mar 23rd to Mar 27th)
Week 11 (Mar 30th to Apr 3rd)
Week 12 (Apr 6th to Apr 10th)
Week 13 (Apr 13th to Apr 17th)
Week 14 (Apr 20th to Apr 24th)
Week 15 (Apr 27th to May 1st)
Week 16 (May 4th to May 8th)