|
1.
|
1/16
|
Introduction
Course summary
(PS,
tex)
Notes - Quicksort/BSP
(ps, tex)
|
| 2. | 1/18 | Minimum Cut (1.1),
Las Vegas and Monte Carlo algorithms (1.2) |
| 3. | 1/23 |
Game Tree Evaluation (2.1),
Occupancy problems (3.1)
The Markov and Chebyshev Inequalities (3.2)
|
| 4. | 1/25 |
Markov's inequality, Chebyshev's inequality, Lazy Select
(html,
ps,
latex
)
|
| 5. | 1/30 |
3.4 Two point sampling, 3.6 The coupon collector's problem (3.6.!),
|
| 6. | 2/1 |
4.1 Chernoff Bound, 4.2 Routing in a parallel computer
(html,
ps,
latex).
|
| 7. | 2/6 |
4.3 A wiring problem - random rounding |
| 8. | 2/8 |
8.2 Random Treaps |
| 9. | 2/13 |
8.3 Skip list, 8.4 Hash Tables
|
| 10. | 2/15 |
8.5 Hashing with O(1) Search Time
|
| 11. | 2/20 |
PAC Learning and VC Dimension
|
| 12. | 2/22 | Proving the existance of
small epsilon-nets (Alon & Spencer 220-230) |
| 13. | 2/27 | Small epsilon-nets -
cont' + range-searching data-structures |
| 14. | 3/1 | 9.2 Another variant of
quick-sort and Convex hull in the plane. Introduction to Clarkson
abstract framework. |
| 15. | 3/6 | The exponential decay
lemma, clarkson bound on the sum of squared expectations, cuttings,
convex-hull in 3d. |
| 16. | 3/8 |
Vertical decomposition, Diameter in 3d.
|
| | 3/13 | Spring Vacation |
| | 3/15 | Spring Vacation |
| 17. | 3/20 |
9.10 Linear programming.
|
| 18. | 3/22 |
10.1 All pairs shortest path |
| 19. | 3/27 |
Witnesses for binary matrix multiplication |
| 20. | 3/29 | Faster Min-Cut
algorithm |
| 21. | 4/3 | Linear time MST |
| 22. | 4/5 | Number theory and
algebra |
| 23. | 4/10 |
Primality testing
|
| 24. | 4/12 | Sphere in higher
dimensions and its concentration of mass |
| 25. | 4/17 | The Johnson
Lindenstraus lemma |
| 26. | 4/19 | The probabilistic
method - 5.1, 5.2 |
| 27. | 4/24 | 5.3 Expanding graphs,
5.3.1 Probability Amplification |
| 28. | 4/26 | MAX
CUT/MAX 2SAT Approximation using Semi-definite programming |
| 29. | 5/1 | Approximate NN search and locality sensitive hashing
|