| Date |
Topic |
Readings |
Handout |
| jan 16 |
Introduction; Identity testing; Randomized min-cut; |
|
[pdf]
|
| jan 23 |
Binomial, geometric distributions; Coupon collecting; Quicksort |
MU 1.4, 2.1-4
|
[pdf] |
| jan 30 |
Markov's, Chebyshev's inequality; Randomized median finding |
MU 2.5, 3.1-3
|
[pdf] |
| feb 6 |
Chernoff Bound; birthday problem; balls & bins |
MU 3.3-4, 5.1-2
|
[pdf] |
| feb 13 |
Random graphs; probabilistic method |
MU 5.1-2
|
[pdf] |
| feb 20 |
Probabilistic method & derandomization |
MU 5.6.1, 6.4
|
[pdf] |
| feb 27 |
Power of two random choices |
MU 14.1
|
[pdf] |
| mar 6 |
Randomized 2-SAT, random walks |
MU 7.1,7.4
|
|
| mar 20 |
Sublinear-time algorithms |
survey pp 1-3
|
[pdf] |
| mar 27 |
Expander graphs |
|
[pdf] |
| apr 3 |
student presentations ?? (topics) |
|
|
| apr 10 |
student presentations I (topics) |
|
|
| apr 17 |
student presentations II |
|
|
| apr 24 |
student presentations III |
|
|