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, simplex. |
NB |
L27 |
| 04/19 |
|
| 04/22 |
No lecture |
|
|
(Independent time for project) |
| 04/24 |
|
| 04/26 |
|
28
| 04/29 |
Randomized rounding: max-cut, set balancing, set cover, routing/wiring, derandomization. |
NB, NB |
L28 |
29
| 05/01 |
Semidefinite programming: max-cut, embeddings, graph coloring. Markov chains 1. |
NB, NB |
L29 |
| 05/03 |
No lecture |
30
| 05/06 |
Markov chains 2: random walks. |
NB |
L30 |
31
| 05/08 |
Markov chains 3: bipartite matching, sampling, and MCMC. |
NB, NB |
L31 |
| 05/10 |
No lecture |
32 |
05/13 |
Peer editing session. |
|
|
(Required attendance!!) |
| 05/15 |
No lecture |
| 05/16 |
--- |
|
|
(Last day of classes) |