6.856J/18.416J Randomized Algorithms (Spring 2021)

Lecture: 2:30-4 Monday, Wednesday, Friday
Units: 5-0-7 G H-Level Grad Credit
Instructor: David Karger karger@mit.edu
TAs: Thiago Bergamaschi thiagob@mit.edu
  Yinzhan Xu xyzhan@mit.edu
  Office hours: 5:30-6:30pm, 10-11pm on Monday and 4-5pm on Friday in this Comingle room

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.

Course Information

There is no course text. However, about half the material we cover can be found in 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


Due Date and Late Submission


Peer Grading

Problem Sets Due Dates Solutions Grading Supervisors Gradescope Code Peer Grading Sign-up Late Submission Form
PS 1 Wed, Feb. 24 PS 1 Sol Thiago 6PK35V PS 1 Graders PS 1 Late Form
PS 2 Wed, Mar. 3 PS 2 Sol Yinzhan 6PXVKV PS 2 Graders PS 2 Late Form
PS 3 Wed, Mar. 10 PS 3 Sol Yinzhan ER6EVE PS 3 Graders PS 3 Late Form
PS 4 Wed, Mar. 17 PS 4 Sol Thiago KYNBJ8 PS 4 Graders PS 4 Late Form
PS 5 Fri, Mar. 26 PS 5 Sol Yinzhan X385XN PS 5 Graders PS 5 Late Form
PS 6 Wed, Mar. 31 PS 6 Sol Yinzhan ZRJX4B PS 6 Graders PS 6 Late Form
PS 7 Wed, Apr. 7 PS 7 Sol Thiago 2RERD3 PS 7 Graders PS 7 Late Form
PS 8 Wed, Apr. 14 Yinzhan JBN78Y PS 8 Graders PS 8 Late Form
PS 9 Fri, Apr. 23 Yinzhan P5RRE7 PS 9 Graders PS 9 Late Form
PS 10 Fri, Apr. 30 Yinzhan P5RB3Y PS 10 Graders PS 10 Late Form
Project Wed, May. 19 David Email staff by 4pm


Lecture Date Topic Notes Recording Scrawls
1 02/17 Introduction to Randomized Algorithms. Quicksort, BSP. NB L01 L01
2 02/19 Min-cut, Complexity theory, Adelman's theorem. NB L02 L02
3 02/22 Game tree evaluation, game theory, lower bounds 1. NB L03 L03
4 02/24 Coupon Collecting, Stable Marriage, and Deviations 1 NB L04 L04
5 02/26 Deviations: Markov, Chebyshev. Median finding 1. NB L05 L05
6 03/01 Pseudorandom numbers. Chernoff bound. NB, NB L06 L06
7 03/03 Randomized routing. NB L07 L07
8 03/05 The Power of Two Choices NB L08 L08
9 03/09 Hashing NB, NB L09 L09 (Monday schedule on Tuesday)
10 03/10 Hashing 2 NB L10 L10
11 03/12 Fingerprinting NB L11 L11
12 03/15 Bloom Filters, Fingerprinting by polynomials, perfect matching. NB, NB L12 L12
13 03/17 Perfect matching, network coding, symmetry breaking. NB L13 L13
14 03/19 Symmetry breaking. Parallel algorithms. Independent set. NB L14 L14
03/22 No lecture (Student Holiday)
15 03/24 Shortest Paths. NB L15 L15
16 03/26 Isolating Lemma. Perfect Matching. Shortest paths 1. NB L16 L16
17 03/29 Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. NB, NB L17
18 03/31 Sampling: transitive closure. DNF counting, rare events. NB, NB L18 L18
19 04/02 Counting versus generation. Minimum spanning tree 1. NB L19 L19
20 04/05 Minimum spanning tree 2. Min-cuts: recursive contraction algorithm 1. NB, NB L20 L20
21 04/07 Min-cuts: recursive contraction algorithm 2. Sampling Minimum Cuts. NB L21 L21
22 04/09 Sampling Cuts NB L22 L22
23 04/12 Network reliability. NB L23 L23
24 04/14 Arrangements of lines. Convex hull via randomized incremental construction 1. NB L24 L24
25 04/16 Convex hull via randomized incremental construction 2. LP: sampling. NB, NB L25 L25
04/19 No lecture (Patriots' Day vacation)
26 04/21 Sampling for LP. NB L26 L26
27 04/23 LP: simplex. Random Answers. NB, NB L27 L27
28 04/26 Randomized rounding. NB, NB L28 L28
29 04/28 Embeddings. NB L29
30 04/30 Metric Embeddings 2. NB L30
31 05/03 Metric Embeddings; Markov chains 1. NB, NB L31
32 05/05 Markov chains 2: random walks. NB L32
33 05/10 Markov chains 3. NB, NB L33
34 05/12 Markov chains 4. NB, NB L34
35 05/17 Peer editing session. (Required attendance!!)
Below this point is subject to change