6.856J/18.416J Randomized Algorithms (Spring 2021)

Lecture: 2:30-4 Monday, Wednesday, Friday (Online Lectures)
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 Yinzhan 6PXVKV PS 2 Graders PS 2 Late Form
PS 3 Wed, Mar. 10 Yinzhan ER6EVE PS 3 Graders PS 3 Late Form


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
7 03/03 Randomized routing. NB L07
8 03/05 The Power of Two Choices NB L08
Below this point is subject to change
9 03/09 Two-choice load balancing 2. Hashing: universal, perfect 1. NB L09 (Monday schedule on Tuesday)
10 03/10 Hashing: perfect 2, cuckoo, consistent 1. NB L10
11 03/12 Hashing: consistent 2. Fingerprinting, string matching 1. NB L11
12 03/15 String matching 2. Bloom Filters. NB L12
13 03/17 Fingerprinting by polynomials, perfect matching, network coding. NB L13
14 03/19 Symmetry breaking. Parallel algorithms. Independent set 1. NB L14
03/22 No lecture (Student Holiday)
15 03/24 Independent set 2. Derandomization. NB L15
16 03/26 Isolating Lemma. Perfect Matching. Shortest paths 1. NB L16
17 03/29 Shortest paths 2. NB L17
18 03/31 Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. NB, NB L18
19 04/02 Sampling: transitive closure. DNF counting, rare events. NB, NB L19
20 04/05 Counting versus generation. Minimum spanning tree 1. NB, NB L20
21 04/07 Minimum spanning tree 2. Min-cuts: recursive contraction algorithm 1. NB, NB L21
22 04/09 Min cuts: recursive contraction algorithm 2, graph sparsification 1. NB L22
23 04/12 Min cuts: graph sparsification 2. Network reliability 1. NB L23
24 04/14 Network realiability 2. Arrangements of lines 1. NB, NB L24
25 04/16 Arrangements of lines 2. Convex hull via randomized incremental construction. NB L25
04/19 No lecture (Patriots' Day vacation)
26 04/21 LP: sampling, randomized incremental construction. NB L26
27 04/23 LP: iterative reweighting, hidden dimension, simplex. NB L27
28 04/26 Randomized rounding: max-cut, set balancing, set cover, routing/wiring, derandomization. NB, NB L28
29 04/28 Semidefinite programming: max-cut, embeddings, graph coloring. Markov chains 1. NB, NB L29
30 04/30 Markov chains 2: random walks. NB L30
31 05/03 Markov chains 3: bipartite matching, sampling, and MCMC. NB, NB L31
32 05/05 Peer editing session. (Required attendance!!)
05/20 --- (Last day of classes)