6.856J/18.416J Randomized Algorithms

Lecture: 2:30-4 Monday, Wednesday, Friday in 4-370
Units: 5-0-7 G H-Level Grad Credit
Instructor: David Karger karger@mit.edu

Course Information

The course text is Randomized Algorithms (link includes errata list). Copies should be available at Quantum Books, and you can also order online at Amazon or Barnes and Noble.

Official catalogue listing

If you are thinking about taking this course, you might want to see what past students have said about previous times I taught Randomized Algorithms, in 2005, 2002, 2000, 1998, and 1996 as well as its sibling course Advanced Algorithms.

Please register for the course by using this form.

You can send anonymous e-mail (praise, complaints, suggestions, ...) to the 6.856 staff by using this form.

Handouts

  1. Course Summary and Info
  2. Problem Set 1, due 2/14/07
  3. Problem Set 2, due 2/21/07

Notes

These notes are my own lecture notes; they will not serve to teach the material but should serve as a record of what was covered in each lecture. Here's a link to Randomized from a previous year.
  1. Lecture 1, 1/31. Introduction to Randomized Algorithms. PDF
  2. Lecture 2, 2/2. Min-Cut, complexity theory, game tree evaluation. PDF
  3. Lecture 3, 2/7. Adelman's Theorem, game theory, lower bounds. PDF
  4. Lecture 4, 2/9. Coupon collecting, stable marriage. PDF.
  5. Lecture 5, 2/11. Deviations. PDF.
  6. Lecture 6, 2/14. Chernoff. PDF,
  7. Lecture 7, 2/16. Load Balance. PDF,
    Scribe notes: Power of 2 Choices. PDF,
  8. Lecture 8, 2/18. Hashing. PDF,
  9. Lecture 9, 2/22. Hashing II. PDF,
  10. Lecture 10, 2/23. Perfect Hashing. PDF,
  11. Lecture 11, 2/28. Fingerprinting. PDF,
    Scribe notes: Bloom Filters. PDF,
  12. Lecture 12, 3/2. Fingerprinting II. PDF,
    Scribe notes: Consistent Hashing. PDF,
  13. Lecture 13, 3/4. Independent set. PDF,
  14. Lecture 14, 3/7. Shortest paths. PDF,
  15. Lecture 15, 3/9. Sampling. PDF,
    Scribe 5: Min-cut estimation. PDF,
  16. Lecture 16, 3/11. Streaming. PDF,
    Scribe 4: Streaming. PDF,
  17. Lecture 17, 3/14. Reliability. PDF,
  18. Lecture 18, 3/16. Approximate Counting. PDF,
    Scribe 6: Random generation of satisfying DNF. PDF,
  19. Lecture 19, 3/30. MST. PDF
  20. Lecture 20, 4/1. Sampling for LP. PDF,
  21. Lecture 21, 4/4. Randomized Rounding. PDF,
  22. Lecture 22, 4/6. Derandomization. PDF,
  23. Lecture 23, 4/8. Embeddings. PDF,
  24. Lecture 25, 4/15. Markov Chains. PDF,
  25. Lecture 27, 4/20. Expanders. PDF,
  26. Lecture 29, 4/22. Markov Chains II. PDF,