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;
Texts:
Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge
Vijay Vazirani, Approximation Algorithms, Springer
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: Uri Feige on random walks.
Other randomized algorithms courses:
By Avrim Blum at CMU.
By David Karger at MIT.
By Anupam Gupta at CMU.
Courses:
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