15-859(M): Randomized Algorithms

Anupam Gupta and Shuchi Chawla
Time: MW 3:00-4:20, Wean 5409

Office Hours: just send mail. We will hold formal office hours if there is enough demand.

Course description: 

Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas. more...

Lecture Notes

  1. Sep 13. (AG) Introduction. (PS, PDF)
  2. Sep 15. (SC) Complexity classes, Identity checking. (PS, PDF) [MR 7.1, 7.2, 7.4]
  3. Sep 20. (SC) Finding perfect matchings randomly. (PS, PDF) [MR 7.3, 12.4]
  4. Sep 22. (AG) Lower bounds on randomized algorithms. (PS, PDF) [MR 2.1, 2.2]
  5. Sep 27. (AG) Randomized Min Cut and related topics. (unedited PS, PDF) [MR 1.1, 10.2]
  6. Sep 29. (AG) Occupancy Problems and Hashing. (unedited PS, PDF) [MR 3.1, 3.6, 8.4].
  7. Oct 4. (AG) Two-level hashing. Markov and Chebychev. (unedited PS, PDF) [MR 8.5, 3.2 + other stuff]
  8. Oct 6. (SC) Sampling, Medians of Means method and DNF counting. (PS, PDF) [MR 11.1, 11.2 + other stuff]
  9. Oct 11. (SC) Chernoff bounds: coin flipping and randomized rounding. (PS, PDF) [MR 4.1 + other stuff]
  10. Oct 13. (AG) Balls and bins: the power of two choices (unedited PS, PDF) [not in MR]
  11. Oct 18. (AG) Randomized Routing, the Probabilistic Method [MR 4.2, 5.3, AS pg.81]
  12. Oct 20. (AG) Lovasz Local Lemma (LLL): Packet Routing Schemes [MR 5.5 + other stuff]
  13. Oct 25. (AG) Lipschitz functions, Martingales, and Concentration of Measure. [MR 4.4, AS Ch.7 (2nd ed.)]
  14. Oct 27. (AG) Martingales (contd.), concentration of geometric TSP  [AS Ch.7 (2nd ed.)]
  15. Nov 01. (SC) Random Walks and Electrical Networks  [MR 6.1--6.5]
  16. Nov 03. (SC) Markov Chains, Rapid Mixing, Conductance  [MR 6.6 + other stuff]
  17. Nov 08. (SC) Rapid mixing in Markov Chains: Conductance and Coupling
  18. Nov 10. (SC) Examples: Colorings, Matchings, Volume Estimation.
  19. Nov 15. (AG) Geometric Algorithms. [MR 9]
  20. Nov 17. (Andrew, Dan G., Nina) Randomized Rounding for Semidefinite Programs.
  21. Nov 22. (Ajit, Jon, Runting) Random sampling for undirected s-t mincuts, (Mohit, Vineet, Vishwanath) Algorithmic Aspects of the Lovasz Local Lemma
  22. Nov 24. Happy thanksgiving (eve)!
  23. Nov 29. (Taka, Anupam) Talagrand's inequality.
  24. Dec 1. (Kaustav, Pradeep) Deviation Bounds for Markov Chains, (David O., Pálli) Load Balancing with Memory
  25. Dec 6. (Shobha, David, Steven) Property Testing, (Florin), (Dan B.) Cuckoo Hashing
  26. Dec 8. (Mugizi, Jeff) Near-neighbor searching, (Sri, Chris)


(Solutions accessible only from within CMU.)
  1. Sep 20. Homework 1. (PS, PDF). (Due Oct 4th.) Solutions
  2. Oct 04. Homework 2. (PS, PDF). (Due Oct 18th.) Solutions
  3. Oct 18. Homework 3. (PS, PDF). (Due Nov 1st.) Solutions
  4. Nov 1. Homework 4. (PS, PDF). (Due Nov 15th in class; no collaboration.) Solutions
  5. Nov 15. Homework 5. (PS, PDF). (Due Nov 29th in class, no collaboration.) Solutions

Misc Documents

  1. Scribe notes LaTeX template here.

Last updated: 12/03/2004