Lecture  Date  Topics  Reading List  SelfStudy 
1 
Jan. 10 
Part 1: The Beauty of Randomization Introduction to random variables Linearity of Expectation and Max 3SAT 
MR 1.0 MU 2.12.5, 1.4 Slides (K. Wayne)  Quicksort MR 1.0 MU 2.5 
2 
Jan. 15 
Randomized Complexity Classes 
MR 1.5 Notes (L. Trevisan)  
3 
Jan 17 
Karger's global mincut algorithm Improved MinCut algorithm by recursion 
Wikipedia  
4 
Jan 22 
Polynomial identity checking Testing Bipartite perfect matchings 
MR 7.1, 7.4 Notes (A. Saberi) 

5 
Jan. 24 
Fingerprinting and Hashing 
MR 7.1, 7.4 

6 
Jan. 29 
Isolation Lemma Perfect matchings via Gaussian elimination 
Notes (A. Saberi) MR 12.4  
7 
Jan. 31 
Part 2: Concentration of Measure Markov and Chebychev Inequalities Randomized Median Finding 
MR 3.13.3 MU 3.13.4  Coupon Collectors MR 3.6 
8 
Feb. 5 
Chernoff Bounds: Derivation and simplification Applications to discrepancy minimization 
MR 4.1, MU 4.2 

9 
Feb. 7 
Sampling and Estimation Techniques Median of means, Importance sampling Approximate counting of combinatorial objects 
MR 11.1, 11.2 

10 
Feb. 12 
Oblivious Routing  MR 4.2, MU 4.5.1  Lovasz Local Lemma (MR 5.5) Notes (A. Srinivasan) 
11 
Feb. 14 
Randomized rounding and congestion  MR 4.3 

12 
Feb. 19 
GoemansWilliamson MaxCUT algorithm 
MAXCUT Paper  
13 
Feb. 21 
Locality Sensitive Hashing  SimHash paper  
14 
Feb. 26 
Tail bounds for occupancy problems Power of two choices 
MR 3.1, 3.6, 4.4.4 Notes (A. Gupta) Presentation (B. Vocking) 
Cuckoo Hashing (Notes) 
15 
Feb. 28 
Martingales: Stopping theorem, Wald's identity Application to Actuarial Science: Lundberg's inequality 
MR 4.4 MU 12.112.3  
16 
Mar. 5 
AzumaHoeffding inequality Balls and Bins; Chromatic number 
MU 12, MR 4.4 

17 
Mar. 7 
Average case analysis: Euclidean TSP and Karp's Heuristic Tour lengths in Euclidean TSP 
Notes Notes Notes (A. Gupta)  
SPRING BREAK 

18 
Mar. 19 
Part 3: Markov Chains and Monte Carlo Randomized algorithm for 3SAT 
MU 7 

19 
Mar. 21 
Stationary distributions Random walks on graphs 
MU 7 

20 
Mar. 26 
M/M/1 queue Metropolis algorithm 
MU 8.6 MU 10.4 

21 
Mar. 28 
Coupling and Mixing times Uniform sampling of independent sets 
MU 11 

22 
Apr. 2 
<< SLACK >> 

23 
Apr. 4 
Part 4: Miscellaneous Luby's maximal independent set algorithm 
MR 12.3 
How it's done in nature 
24 
Apr. 9 
Weighted majority algorithm  Notes  
25 
Apr. 11 
Yao's minmax principle and lower bounds Zerosum games 
Notes  
26 
Apr. 16 
Take Home FINAL 
