6.856J/18.416J Randomized Algorithms

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

Course Announcements

The project guidelines has been uploaded here. Use this spreadsheet to look for project collaborators if needed.
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.

NB Discussion System

I'll be posting notes and handouts in NB. NB is a discussion forum, but you post your questions/replies in the margins of the documents you're discussing. Feel free to use nb to ask clarification questions about the homework, but don't discuss answers---that's for you to do in your small groups.

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

Course Information

The course text is Randomized Algorithms (link includes errata list). Copies should be available at the Coop. You can also order online at Amazon or Barnes and Noble.

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.

Problem Sets

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 subproblem 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	PS 1 Sol	Pritish	[P1] Pritish Kamath; [P2, P3] Irene Chen (iychen), Helen Xu (hjxu); [P4, P5] Max Murin (maxmurin), Daniel Ziegler (dmz); [P6, P7] Salman Salamatian (salmansa), Yuancheng Yu (ycyu)
PS 2	Wed, Feb. 21	PS 2 Sol	Pritish	[P1] Benson Chen (bensonc), Yinzhan Xu (xyzhan); [P2] Linh Nguyen (lvnguyen); [P3] Tao Du (taodu); [P4] Giancarlo Sturla (sturlag)
PS 3	Wed, Mar. 1	PS 3 Sol	Pritish	[P2] Cenk Baykal (baykal); [P3] Vikram Nathan (vikramn); [P4] Sammy Luo (sammyluo); [P5] Kevin Yang (yangk)
PS 4	Wed, Mar. 8	PS 4 Sol	Pritish	[P1] Mehrdad Khani Shirkoohi (khani); [P2, P5] Darsh Shah (darsh); [P3] Jie Xu (jiex); [P4] Wilko Schwarting (wilkos)
PS 5	Wed, Mar. 15	PS 5 Sol	Pritish	[P1] Elaheh Fata (efata); [P2] Hao Shen (haoshen); [P3] Andrew He (andrewhe); [P4] Valerio Varricchio (valerio)
PS 6	Wed, Mar. 22	PS 6 Sol	Pritish	[P1] Lucas Liebenwein (lucasl); [P2] Wengong Jin (wengong); [P3] Vishesh Jain (visheshj); [P4] Shalom Abate (shaladi); [P5] Ferran Alet (alet)
PS 7	Wed, Apr. 5	PS 7 Sol	Pritish	[P1] Feras Saad (fsaad); [P2] Rohan Chitnis (ronuchit); [P3] Liang Shi (liangs); [P4] Jason Altschuler (jasonalt); [P5] Matthew Brennan (brennanm); [P6] Bobby Shen (runbobby)
PS 8	Wed, Apr. 12	PS 8 Sol	Pritish	[P1] Peter Ahrens (pahrens); [P2] Georgios Vlachos (gvlachos); [P3] Rishad Rahman (rrrahman); [P4] Lawrence Li (lawli)
PS 9	Wed, Apr. 19	PS 9 Sol	Pritish	[P1] Sanjeev Murty (smurty); [P2] Tong Wang (twang6); [P3] Lawrence Sun (sunl)
PS 10	Wed, Apr. 26	PS 10 Sol	Pritish	[P1] Nicholas Schiefer (schiefer); [P2] Alexander Clifton (aclifton); [P3] Paolo Gentili (pgentili); [P4] Lyuboslav Panchev (lpanchev)
PS 11	Wed, May. 3	PS 11 Sol	Pritish	[P1-P5] Pritish

Notes

These notes reflect a starting plan that may change. They 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. Note that all course notes can be found in nb, where you can read and annotate them with questions.

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. Two-choice load balancing (NB).
Lecture 8, 2/27. Hashing. universal (NB), perfect, cuckoo (NB).
Lecture 9, 3/1. Fingerprinting. String Matching. Bloom Filters (NB).
Lecture 10, 3/3. Bloom Filters, Fingerprinting II, Consistent Hashing
Lecture 11, 3/6. Fingerprinting by Polynomials. Perfect Matching. (NB)
Lecture 12, 3/8. Symmetry Breaking. Isolating Lemma. Finding perfect matchings. (NB)
Lecture 13, 3/10. Independent set. Derandomization (NB)
Lecture 14, 3/13. Shortest Paths. (NB).
Lecture 15, 3/15. Sampling. Transitive Closure. (NB).
Lecture 16, 3/17. Rare Events. DNF Counting. (NB).
Lecture 17, 3/20. Counting Versus Generation. MST. (NB)
Lecture 18, 3/22. Recursive Contraction (with min-cut notes). (NB)
Lecture 19, 3/24. Graph sparsification. Minimum Cut.
3/27-3/31. Spring break.
Lecture 20, 4/3. Network reliability. Geometry. Arrangements of Lines. (NB)
Lecture 21, 4/5. Randomized Incremental Construction: Convex Hull.
Lecture 22, 4/7. Sampling for LP. Iterative reweighting. Randomized incremental construction. Hidden Dimension. (NB)
Lecture 23, 4/10. Finish hidden dimension. Begin approximation algorithms. Randomized Rounding. Max-cut.
Lecture 24, 4/12. Randomized rounding: max-SAT (NB).
4/14. Likely no lecture
4/17. Patriots' Day Vacation.
Lecture 25, 4/19. Randomized rounding: Set Bias; wiring; derandomization (NB).
Lecture 26, 4/21. Max-cut by SDP. Begin Bisection/Separator (NB).
Lecture 27, 4/24. Embeddings. Ratio cut.
Lecture 28, 4/26. Markov chains. (NB set)
Lecture 29, 4/28. More Markov chains. Expanders. (NB set)
Lecture 30, 5/1. Markov Chains for Sampling (NB set)
5/15. Peer editing session (attendance required).
5/17. Last day of class

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