Lecture: | 2:30-4 Monday, Wednesday, Friday in 32-124 | ||

Units: | 5-0-7 | ||

Instructor: |
David Karger
karger@mit.edu
| ||

TA: |
Pritish Kamath
pritish@csail.mit.edu
| ||

Office Hours: | 4-5pm Monday and Friday in CSAIL 5th floor lounge | ||

- Please fill out this course signup form so we can build a class mailing list and grading sheet.
- Use this spreadsheet to search for PSet collaborators.
- In the current problem set 2, problem 3 depends on material I will be covering next lecture. Thus, I am extending the deadline for
**problem 3 only**to Friday 2/24.

You can subscribe to the NB class site using this link.

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 2013, 2005, or 2002.

- Homework is due Wednesdays at the
**beginning**of class. We'll have boxes or piles for dropping them off at the back of the room. Those boxes will be collected a few minutes in, and homework arriving after will be considered late. - Each student has a total budget of 15 "slack" points to accommodate his/her late problem submissions. Each
**problem**that is submitted late but in before Friday class will consume**one**slack point (and incur no grade penalty). If that problem is submitted in before Monday class, it will consume**two**slack points (and, again, incur no grade penalty). No late problem will be considered if submitted after the Monday class begins. (So, for example, if there is a problem set with a total of five problems on it, submitting three of these problems on time, one of them before Friday class, and one of them before Monday class will consume three slack points in total.) - Write each
**sub**problem on a**separate**sheet of paper and include your name and email address. Also, make sure your name appears on**each**page. - Collaboration is strongly encouraged except where
explicitly forbidden. However, each person must independently write
up his/her own solution, and you must list all collaborators for
**each**problem on your problem set. Collaboration groups should be small (3 or 4 students) to ensure that everyone is actively engaged with the problems. - You may not seek out answers from other sources without prior permission. In particular, you may not use bibles or posted solutions to problems from previous years.
- Each student is required to grade (at least but hopefully) one problem in the semester. We will have a TA-supervised grading session each week. This session is used to make sure that the graders fully understand the solution, while they can grade the problems at home after this session.
- For questions about grading, please contact the graders (emails listed on the website) first. Once you reach an agreement, the grader should send an email to the grading supervisor with a short explanation and a new grade.
- All late psets should be sent electronically to the TA supervising the grading.

Problem Sets | Due Dates | Solutions | Grading Supervisors | Graders |
---|---|---|---|---|

PS 1 | Fri, Feb. 17 | Pritish | ||

PS 2 | Wed, Feb. 21 | Pritish | ||

PS 3 | Wed, Mar. 1 | Pritish |

- Lecture 1, 2/8. Introduction to Randomized Algorithms. Quicksort, BSP, Min-cut. (NB)
- Lecture 2, 2/10. complexity theory, Adelman's theorem, game tree evaluation. (NB)
- 2/13. Class cancelled due to snow storm.
- Lecture 3, 2/15. game theory, lower bounds, Coupon collecting, stable marriage. (NB)
- Lecture 4, 2/17. Deviations: Markov, Chebyshev. (NB)
- Lecture 5, 2/21 (Tuesday as Monday). Median Finding. (NB)
- Lecture 6, 2/22. Chernoff bound (NB) Randomized routing (NB).
- Lecture 7, 2/24. Balls in bins.
- Lecture 8, 2/27. Two-choice load balancing (NB).
- Lecture 9, 3/1. Hashing. universal (NB), perfect, cuckoo (NB).
- Lecture 10, 3/3. Consistent Hashing. Fingerprinting. (NB).
- Lecture 11, 3/6. Fingerprinting II. String Matching. Bloom Filters
- Lecture 12, 3/8. Fingerprinting by Polynomials. Perfect Matching. (NB)
- Lecture 13, 3/10. Symmetry Breaking. Isolating Lemma. Finding perfect matchings. (NB)
- Lecture 14, 3/13. Independent set. (NB)
- Lecture 15, 3/15. IS Derandomization. Shortest Paths. (NB).
- Lecture 16, 3/17. Finish Shortest Paths. Sampling. (NB).
- Lecture 17, 3/20. Transitive closure. Rare Events. DNF Counting. (NB).
- Lecture 18, 3/22. Counting Versus Generation. MST. (NB)
- Lecture 19, 3/24. Recursive Contraction (with min-cut notes). (NB)
- 3/27-3/31. Spring break.
- Lecture 20, 4/3. Graph sparsification. Minimum Cut.
- Lecture 21, 4/5. Network reliability. Geometry. Arrangements of Lines. (NB)
- Lecture 22, 4/7. Randomized Incremental Construction: Convex Hull.
- Lecture 23, 4/10. Sampling for LP. Iterative reweighting. Randomized incremental construction. Hidden Dimension. (NB)
- Lecture 24, 4/12. Finish hidden dimension. Begin approximation algorithms. Randomized Rounding. Max-cut.
- 4/14. Likely no lecture
- 4/17. Patriots' Day Vacation.
- Lecture 25, 4/19. Randomized rounding: max-SAT (NB).
- Lecture 26, 4/21. Randomized rounding: Set Bias; wiring; derandomization (NB).
- Lecture 27, 4/24. Max-cut by SDP. Begin Bisection/Separator (NB).
- Lecture 28, 4/26. Embeddings. Ratio cut.
- Lecture 29, 4/28. Markov chains. (NB set)
- Lecture 30, 5/1. More Markov chains. Expanders. (NB set)
- Lecture 31, 5/3. Markov Chains for Sampling (NB set)
- 5/15. Peer editing session (attendance required).
- 5/17. Last day of class