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 Lucas PS 5 Submission PS 5 Graders PS 5 Late Form
PS 6 Wed, Mar. 20 Sam PS 6 Submission PS 6 Graders PS 6 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
19 03/20 Rare events. DNF counting. Counting versus generation. Minimum spanning tree.
20 03/22 Recursive contraction (with min-cuts). Graph sparsification. Minimum cut.
03/25
03/27 No lecture (Spring vacation)
03/29
21 04/01 Network reliability. Geometry.
22 04/03 Arrangements of lines. Randomized incremental construction: convex hull.
23 04/05 Sampling for LP. Iterative reweighting. Randomized incremental construction. Hidden dimension.
24 04/08 Randomized rounding: max-cut, max-SAT.
25 04/10 Randomized rounding 2: set bias, wiring, derandomization.
26 04/12 Max-cut by semidefinite programming (SDP). Begin bisection/separator.
04/15 No lecture (Patriots' Day vacation)
27 04/17 Embeddings. Ratio cut.
28 04/19 Markov chains 1.
29 04/22 Markov chains 2. Expanders.
30 04/24 Markov chains 3: sampling.
31 05/15 Peer editing session. (Required attendance!!)
05/16 --- (Last day of classes)