6.5220J/6.856J/18.416J Randomized Algorithms (Spring 2025) (original) (raw)
1
09/03
Introduction to Randomized Algorithms. Quicksort, BSP.
2
09/05
Min-cut, Complexity theory.
3
09/08
Adelman's theorem, Game tree evaluation.
4
09/10
Game theory, Lower bounds 1, Coupon collecting, Stable marriage
5
09/12
Deviations: Markov, Chebyshev. Balls in Bins.
6
09/15
Median finding. Pseudorandom numbers.
7
09/17
Chernoff bound. Randomized routing.
09/19
No lecture
(Student Holiday)
8
09/22
The Power of Two Choices
9
09/24
Universal and Perfect Hashing (prerecorded)
10
09/26
Two choices (cont). Cuckoo Hashing.
11
09/29
Consistent Hashing. Fingerprinting.
12
10/01
Text search. Bloom filters.
13
10/03
Fingerprinting by polynomials, Perfect matching. Network coding.
14
10/06
Symmetry breaking. Parallel algorithms. Ethernet. Parallel perfect matching.
15
10/8
Shortest Paths (prerecorded).
16
10/10
Parallel Maximal independent set. Derandomization.
10/13
No lecture
(Indigenous Peoples' Day)
17
10/15
Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items.
18
10/17
Sampling: transitive closure. DNF counting, rare events.
19
10/20
Counting versus generation. Minimum spanning tree.
20
10/22
Min-cuts: recursive contraction algorithm.
21
10/24
Sampling for approximate min-cuts.
22
10/27
Sampling for exact min-cut. Network Reliability
23
10/29
Computational Geometry. Point Location in an arrangement of lines
24
10/31
Convex hull via randomized incremental construction. LP
25
11/03
LP: sampling.
26
11/05
More sampling for LP. Seidel+hidden dimension.
27
11/07
LP: simplex. The probabilistic method.
11/10
No lecture
(Student holiday)
28
11/12
Randomized rounding.
29
11/14
Embeddings.
30
11/17
Metric Embeddings 2.
31
11/19
Metric Embeddings; Markov chains 1.
32
11/21
Markov chains 2: random walks.
33
11/24
Markov chains 3.
34
11/26
Markov chains 4.
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