| |
|
| Date |
Topic |
Reading |
Exercises |
| W 08/28 |
Introduction |
MR 1.1, 1.2, 1.3 |
|
| M 09/02 |
LABOR DAY |
|
|
| W 09/04 |
Moments and deviations |
MR 3.1, 3.2, 3.3 |
1 out |
| M 09/09 |
Moments and deviations |
MR 3.4, 3.5, 3.6 |
|
| W 09/11 |
The min-cut problem |
MR 10.2 |
|
| M 09/16 |
Minimum spanning trees |
MR 10.3 |
1 solutions |
| W 09/18 |
Chernoff bounds |
MR 4.1 |
2 out |
| M 09/23 |
Applications of Chernoff bounds |
|
|
| W 09/25 |
Hypercube routing |
MR 4.2 |
|
| M 09/30 |
Random treaps |
MR 8.2 |
2 solutions |
| W 10/02 |
TEST 1 |
|
|
| M 10/07 |
Skip lists |
MR 8.3 |
3 out |
| W 10/09 |
Hash tables |
MR 8.4 |
|
| M 10/14 |
Cuckoo hashing |
|
|
| W 10/16 |
Tabulation hashing |
|
3 solutions, 4 out |
| M 10/21 |
Martingales |
MR 4.4 |
|
| W 10/23 |
The probabilistic method |
MR 5.1, 5.2 |
|
| M 10/28 |
The probabilistic method |
MR 5.3, 5.4 |
|
| W 10/30 |
The probabilistic method |
MR 5.5 |
4 solutions |
| M 11/04 |
TEST 2 |
|
|
| W 11/06 |
The probabilistic method |
MR 5.6 |
5 out |
| M 11/11 |
Markov chains and random walks |
MR 6.1, 6.2 |
|
| W 11/13 |
Markov chains and random walks |
MR 6.3, 6.5, 6.6 |
|
| M 11/18 |
Markov chains and random walks |
MR 6.7, 6.8 |
5 solutions |
| W 11/20 |
DNF counting |
MR 11.2 |
6 out |
| M 11/25 |
Maximal independent sets |
MR 12.3 |
|
| W 11/27 |
Perfect matchings |
MR 12.4 |
|
| M 12/02 |
Paging against an oblivious adversary |
MR 13.3 |
6 solutions |
| W 12/04 |
TEST 3 |
|
|