1
| 02/17 |
Introduction to Randomized Algorithms. Quicksort, BSP. |
NB |
L01 |
L01 |
2
| 02/19 |
Min-cut, Complexity theory, Adelman's theorem. |
NB |
L02 |
L02 |
3
| 02/22 |
Game tree evaluation, game theory, lower bounds 1. |
NB |
L03 |
L03 |
4
| 02/24 |
Coupon Collecting, Stable Marriage, and Deviations 1 |
NB |
L04 |
L04 |
5
| 02/26 |
Deviations: Markov, Chebyshev. Median finding 1. |
NB |
L05 |
L05 |
6
| 03/01 |
Pseudorandom numbers. Chernoff bound. |
NB, NB |
L06 |
L06 |
7
| 03/03 |
Randomized routing. |
NB |
L07 |
L07 |
8
| 03/05 |
The Power of Two Choices |
NB |
L08 |
L08 |
9
| 03/09 |
Hashing |
NB, NB |
L09 |
L09 |
(Monday schedule on Tuesday) |
10
| 03/10 |
Hashing 2 |
NB |
L10 |
L10 |
11
| 03/12 |
Fingerprinting |
NB |
L11 |
L11 |
12
| 03/15 |
Bloom Filters, Fingerprinting by polynomials, perfect matching. |
NB, NB |
L12 |
L12 |
13
| 03/17 |
Perfect matching, network coding, symmetry breaking. |
NB |
L13 |
L13 |
14
| 03/19 |
Symmetry breaking. Parallel algorithms. Independent set. |
NB |
L14 |
L14 |
| 03/22 |
No lecture |
|
|
|
(Student Holiday) |
15
| 03/24 |
Shortest Paths. |
NB |
L15 |
L15 |
16
| 03/26 |
Isolating Lemma. Perfect Matching. Shortest paths 1. |
NB |
L16 |
L16 |
17
| 03/29 |
Sampling: polling. Streaming algorithms: frequent items, sketches, distinct items. |
NB, NB |
L17 |
|
18
| 03/31 |
Sampling: transitive closure. DNF counting, rare events. |
NB, NB |
L18 |
L18 |
19
| 04/02 |
Counting versus generation. Minimum spanning tree 1. |
NB |
L19 |
L19 |
20
| 04/05 |
Minimum spanning tree 2. Min-cuts: recursive contraction algorithm 1. |
NB, NB |
L20 |
L20 |
21
| 04/07 |
Min-cuts: recursive contraction algorithm 2. Sampling Minimum Cuts. |
NB |
L21 |
L21 |
22
| 04/09 |
Sampling Cuts |
NB |
L22 |
L22 |
23
| 04/12 |
Network reliability. |
NB |
L23 |
L23 |
24
| 04/14 |
Arrangements of lines. Convex hull via randomized incremental construction 1. |
NB
| L24 |
|
25
| 04/16 |
Convex hull via randomized incremental construction 2. LP: sampling. |
NB, NB |
L25 |
|
| |
Below this point is subject to change
|
| 04/19 |
No lecture |
|
|
|
(Patriots' Day vacation) |
26
| 04/21 |
LP: sampling, randomized incremental construction. |
NB |
L26 |
|
27
| 04/23 |
LP: iterative reweighting, hidden dimension, simplex. |
NB |
L27 |
|
28
| 04/26 |
Randomized rounding: max-cut, set balancing, set cover, routing/wiring, derandomization. |
NB, NB |
L28 |
|
29
| 04/28 |
Semidefinite programming: max-cut, embeddings, graph coloring. Markov chains 1. |
NB, NB |
L29 |
|
30
| 04/30 |
Markov chains 2: random walks. |
NB |
L30 |
|
31
| 05/03 |
Markov chains 3: bipartite matching, sampling, and MCMC. |
NB, NB |
L31 |
|
32 |
05/05 |
Peer editing session. |
|
|
|
(Required attendance!!) |
| 05/20 |
--- |
|
|
|
(Last day of classes) |