|04/01/10||Introduction||Quicksort||Read Chapter 1
Karp, An introduction to randomized algorithms, Discrete Applied Mathematics 34 (1991), 165-201.
|06/01/10||Background Tour||Vertex Cover, Matching|
|11/01/10||Pivots for Approximation Algs||Min Feedback Arc Set in Tournaments||Ailon, Charikar, and Newman, Aggregating Inconsistent Information: Ranking and Clustering, STOC 2005.|
|13/01/10||Monte Carlo, Boosting, Saving Computation||Global Min-Cut||Read Chapter 1 and Chapter 10|
|18/01/10||NO CLASS - MLK DAY|
|20/01/10||Lower Bounds for Randomized Algorithms||Game Tree Evaluation||Read Chapter 2
Complete Problem Set 1 (due Feb. 1st)
|25/01/10||Tail Bounds -- Markov, Chebyshev||Randomized Selection||Read Chapter 3|
|27/01/10||Tail Bounds -- Chernoff||Routing in Hypercubes, Power of Two Choices Load Balancing||Read Chapter 4
Azar, Broder, Karlin, and Upfal, Balanced Allocations, SIAM J. on Computing 29 (1999), 180-200.
|01/02/10||PROBLEM SET 1 PRESENTATIONS||problem 1, problem 2, problem 3, problem 4|
|03/02/10||Hashing||Chaining, Linear Probing||Mihai's wonderful blog posts here
Pagh, Pagh, and Ruzic, Linear Probing with Constant Independence, STOC 2007.
|08/02/10||Hashing, Randomized Rounding LPs||Cuckoo Hashing, Max-SAT||Mihai's wonderful blog post here, Williamson-Shmoy Chapter 5.|
|15/02/10||Randomized Rounding SDPs||Max Cut||Williamson-Shmoy Chapter 6.|
|17/02/10||Metric Embeddings||Sparsest Cut||Vazirani, Chapter 21.|
|19/02/10||GUEST LECTURE: Azarakhsh Malekian on Random Sampling Auctions|
|22/02/10||Online Pimal-Dual||Ski Rental||Survey by Buchbinder and Naor|
|24/02/10||GUEST LECTURE: Lance Fortnow on The Power of Randomization|
|26/02/10||Multi-Armed Bandits||Allocating Sponsored Search Ads|
|01/03/10||Markov Chains||Card Shuffling||Motwani-Raghavan, Chapter 6; Sinclair's course (see below).|
|03/03/10||FINAL PROJECT PRESENTATIONS|