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 Pritish [P1] Mehrdad Khani Shirkoohi (khani); [P2+P5] Darsh Shah (darsh); [P3] Jie Xu (jiex); [P4] Wilko Schwarting (wilkos)
PS 5 Wed, Mar. 15 Pritish [P1] Elaheh Fata (efata); [P2] Hao Shen (haoshen); [P3] Andrew He (andrewhe); [P4] Valerio Varricchio (valerio)
PS 6 Wed, Mar. 22 Pritish ??
PS 7 Wed, Apr. 5 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.