Lecture | Date | Topics | Reading List | Self-Study |
1 |
Jan. 10 |
Part 1: The Beauty of Randomization Introduction to random variables Linearity of Expectation and Max 3-SAT |
MR 1.0 MU 2.1-2.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.1-3.3 MU 3.1-3.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 |
Goemans-Williamson 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.1-12.3 | |
16 |
Mar. 5 |
Azuma-Hoeffding 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 3-SAT |
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 min-max principle and lower bounds Zero-sum games |
Notes | |
26 |
Apr. 16 |
Take Home FINAL |
|