6.5220/6.856J/18.416J Randomized Algorithms (Spring 2025)

Lecture: 2:30-4 Monday, Wednesday, Friday
Units: 5-0-7 G H-Level Grad Credit
Instructor: David Karger karger@mit.edu
TAs: Junxuan (Helen) Shen junxuan@mit.edu
  Wei Zhang w_zhang@mit.edu
  Office hours: Monday 4-5PM Helen, Stata G5 Lounge
Friday 4-5PM Wei, Stata G5 Lounge

Course Announcements

Problem Sets

Set Due Dates Solutions Grading Supervisors Gradescope Code Peer Grading Sign-up Late Submission Form
PS 1 Wed, Sep. 10 PS1 Solution Wei B3N3KJ PS 1 Graders PS 1 Late Form
PS 2 Wed, Sep. 17 PS2 Solution Helen J6XE57 PS 2 Graders PS 2 Late Form
PS 3 Wed, Sep. 24 PS3 Solution Wei D3VRWW PS 3 Graders PS 3 Late Form
PS 4 Wed, Oct. 1 PS4 Solution Helen EE88VY PS 4 Graders PS 4 Late Form
PS 5 Wed, Oct. 8 PS5 Solution Wei VW366R PS 5 Graders PS 5 Late Form
PS 6 Wed, Oct. 15 PS6 Solution Helen ZY7WXR PS 6 Graders PS 6 Late Form
PS 7 Wed, Oct. 22 PS7 Solution Wei X2WBK3 PS 7 Graders PS 7 Late Form
PS 8 Wed, Oct. 29 PS8 Solution Helen E654RB PS 8 Graders PS 8 Late Form
PS 9 Wed, Nov. 5 PS9 Solution Wei 2DGZ4Y PS 9 Graders PS 9 Late Form
PS 10 Wed, Nov. 12 PS10 Solution Helen E6R6DK PS 10 Graders PS 10 Late Form
PS 11 Wed, Nov. 19 Wei KNYP5J PS 11 Graders PS 11 Late Form
PS 12 Wed, Nov. 26 Helen KN3YV7 PS 12 Graders PS 12 Late Form

Lectures

Lecture Date Topic Notes Recording Scrawls & Recordings (old)
1 09/03 Introduction to Randomized Algorithms. Quicksort, BSP. NB L1 L01, L01
2 09/05 Min-cut, Complexity theory. NB L2 L02, L02
3 09/08 Adelman's theorem, Game tree evaluation. NB L3 L03, L03
4 09/10 Game theory, Lower bounds 1, Coupon collecting, Stable marriage NB L4 L04, L04
5 09/12 Deviations: Markov, Chebyshev. Balls in Bins. NB L5 L05, L05
6 09/15 Median finding. Pseudorandom numbers. NB, NB L6 L06, L06
7 09/17 Chernoff bound. Randomized routing. NB L7 L07, L07
09/19 No lecture (Student Holiday)
8 09/22 The Power of Two Choices NB L8 L08, L08
9 09/24 Universal and Perfect Hashing (prerecorded) NB, NB L9 L09, L09
10 09/26 Two choices (cont). Cuckoo Hashing. NB L10 L10, L10
11 09/29 Consistent Hashing. Fingerprinting. NB L11 L11, L11
12 10/01 Text search. Bloom filters. NB, NB L12 L12, L12
13 10/03 Fingerprinting by polynomials, Perfect matching. Network coding. NB L13 L13, L13
14 10/06 Symmetry breaking. Parallel algorithms. Ethernet. Parallel perfect matching. NB L14 L14, L14
15 10/8 Shortest Paths (prerecorded). NB L16, L16
16 10/10 Parallel Maximal independent set. Derandomization. NB L16 L15, L15
10/13 No lecture (Indigenous Peoples' Day)
17 10/15 Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. NB, NB
18 10/17 Sampling: transitive closure. DNF counting, rare events. NB, NB L18 L18, L18
19 10/20 Counting versus generation. Minimum spanning tree. NB L19 L19, L19
20 10/22 Min-cuts: recursive contraction algorithm. NB, NB L20 L20, L20
21 10/24 Sampling for approximate min-cuts. NB L21 L21, L21
22 10/27 Sampling for exact min-cut. Network Reliability NB L22 L22, L22
23 10/29 Computational Geometry. Point Location in an arrangement of lines NB L23 L23,L23
24 10/31 Convex hull via randomized incremental construction. LP NB, NB L24 L24, L24
25 11/03 LP: sampling. NB L25 L25, L25
26 11/05 More sampling for LP. Seidel+hidden dimension. NB L26 L26, L26
27 11/07 LP: simplex. The probabilistic method. NB, NB L27 L27, L27
11/10 No lecture (Student holiday)
28 11/12 Randomized rounding. NB, NB L28 L28
29 11/14 Embeddings. NB L29
30 11/17 Metric Embeddings 2. NB L30
31 11/19 Metric Embeddings; Markov chains 1. NB, NB L31
32 11/21 Markov chains 2: random walks. NB L32
33 11/24 Markov chains 3. NB, NB L33
34 11/26 Markov chains 4. NB, NB L34
11/28 No lecture (Institute holiday)
35 12/01
36 12/03
37 12/05
38 12/08 Peer editing session. (Required attendance!!)
39 12/10 (Last day of classes)
Below this point is subject to change