6.856J/18.416J Randomized Algorithms

Lecture: 2:30-4 Monday, Wednesday, Friday in 32-124
Units: 5-0-7 G H-Level Grad Credit
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

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

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


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.