6.856J/18.416J Randomized Algorithms (Spring 2019)

Lecture: 2:30-4 Monday, Wednesday, Friday in 35-225 (ROOM CHANGE)
Units: 5-0-7 G H-Level Grad Credit
Instructor: David Karger karger@mit.edu
TAs: Lucas Liebenwein lucasl@mit.edu
  Sam Park sp765@mit.edu
Office Hours: 4-5pm Monday, Friday in 32-044.

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

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

Submission

Due Date and Late Submission

Policy

Peer Grading



Problem Sets Due Dates Solutions Grading Supervisors Submission Links Peer Grading Sign-up Late Submission Form
PS 1 Wed, Feb. 13 PS 1 Sol Lucas PS 1 Submission PS 1 Graders PS 1 Late Form
PS 2 Wed, Feb. 20 PS 2 Sol Sam PS 2 Submission PS 2 Graders PS 2 Late Form
PS 3 Wed, Feb. 27 PS 3 Sol Lucas PS 3 Submission PS 3 Graders PS 3 Late Form
PS 4 Wed, Mar. 6 PS 4 Sol Sam PS 4 Submission PS 4 Graders PS 4 Late Form
PS 5 Wed, Mar. 13 PS 5 Sol Lucas PS 5 Submission PS 5 Graders PS 5 Late Form
PS 6 Wed, Mar. 20 PS 6 Sol Sam PS 6 Submission PS 6 Graders PS 6 Late Form
PS 7 Wed, Apr. 3 PS 7 Sol Lucas PS 7 Submission PS 7 Graders PS 7 Late Form
PS 8 Wed, Apr. 10 Sam PS 8 Submission PS 8 Graders PS 8 Late Form
PS 9 Wed, Apr. 17 Lucas PS 9 Submission PS 9 Graders PS 9 Late Form

Lectures

Lecture Date Topic Notes Recording
1 02/06 Introduction to Randomized Algorithms. Quicksort, BSP. NB
2 02/08 Min-cut, Complexity theory, Adelman's theorem. NB
3 02/11 Game tree evaluation, game theory, lower bounds 1. NB
4 02/13 Lower bounds 2, coupon collecting, stable marriage. NB L04
5 02/15 Deviations: Markov, Chebyshev. Median finding 1. NB L05
6 02/19 Median finding 2. Pseudorandom numbers. NB L06 (Monday schedule on Tuesday)
7 02/20 Chernoff bound. Randomized routing. NB, NB L07
8 02/22 Two-choice load balancing 1. NB L08
9 02/25 Two-choice load balancing 2. Hashing: universal, perfect 1. NB L09
10 02/27 Hashing: perfect 2, cuckoo, consistent 1. NB L10
11 03/01 Hashing: consistent 2. Fingerprinting, string matching 1. NB L11
12 03/04 String matching 2. Bloom Filters. NB L12
13 03/06 Fingerprinting by polynomials, perfect matching, network coding. NB L13
14 03/08 Symmetry breaking. Parallel algorithms. Independent set 1. NB L14
15 03/11 Independent set 2. Derandomization. NB L15
16 03/13 Isolating Lemma. Perfect Matching. Shortest paths 1. NB L16
17 03/15 Shortest paths 2. NB L17
18 03/18 Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. NB, NB L18
19 03/20 Sampling: transitive closure. DNF counting, rare events. NB, NB L19
20 03/22 Counting versus generation. Minimum spanning tree 1. NB, NB L20
03/25
03/27 No lecture (Spring vacation)
03/29
21 04/01 Minimum spanning tree 2. Min-cuts: recursive contraction algorithm 1. NB, NB L21
22 04/03 Min cuts: recursive contraction algorithm 2, graph sparsification 1. NB L22
23 04/05 Min cuts: graph sparsification 2. Network reliability 1. NB L23
24 04/08 Network realiability 2. Arrangements of lines 1. NB, NB L24
25 04/10 Arrangements of lines 2. Convex hull via randomized incremental construction. NB L25
26 04/12 LP: sampling, randomized incremental construction. NB L26
04/15 No lecture (Patriots' Day vacation)
27 04/17 LP: iterative reweighting, hidden dimension. Randomized rounding: max-cut, max-SAT, set bias, wiring, derandomization.
04/19
04/22 No lecture (Independent time for project)
04/24
04/26
28 04/29 Max-cut by semidefinite programming (SDP). Begin bisection/separator. Embeddings. Ratio cut.
29 05/01 Markov chains 1.
30 05/03 Markov chains 2: expanders.
31 05/06 Markov chains 3: sampling.
32 05/15 Peer editing session. (Required attendance!!)
05/16 --- (Last day of classes)