Homework 1 due 9/9 in pdf. Homework 2 due 10/2 in pdf.
Notes: 8/26 (Quicksort, mincut);
8/28 (Basic inequalities, quickselect,coupon collector); 9/4 (Permutation routing);
Set Cover; Steiner Tree and TSP;
Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge
Vijay Vazirani, Approximation Algorithms, Springer
Overview (rough syllabus).
Books, papers and handouts:
Probabilistic inequalities (from A.Blum)
Bertsimas, Teo, Vohra: Dependent randomized rounding
Link to two surveys on random walks by Lovász
Doyle and Snell: Random walks and electric networks
Related pages: NP Optimization Compendium. Uri Feige on random walks.
Other randomized algorithms courses:
By Avrim Blum at CMU.
By David Karger at MIT.
By Anupam Gupta at CMU.
Metric methods by Anupam Gupta
Algorithmic aspects of game theory by Christos Papadimitriou
Random and high-dimensional algorithms by Jon Kleinberg
Structure of information networks by Jon Kleinberg