Below is a tentative schedule for 15-750 (Spring 2001). Topics subject to change.
Lectures Topic Reading
-----------------------------------------------------------------------------------
1. 01/16 Karatsuba, Strassen, Probability, Qsort chapter 1 and handout
2. 01/18 Treaps Handout & chapter 13
3. 01/23 Amortized analysis and start splay trees chapter 12
4. 01/25 Splay trees contd
5. 01/30 graphs, MST, topological sorting chapters 2, 4
6. 02/01 Union/find chapter 10
7. 02/06 Fibonacci heaps chapters 8, 9
8. 02/08 Linear time MST algorithm (handout?)
9. 02/13 global min cuts (handout?)
10. 02/15 Voronoi diagrams (handout?)
11. 02/20 Planar point location I (persistence) (handout?)
12. 02/22 Planar point location II (Clarkson) (handout?)
13. 02/27 Planar separator theorem chapters 14 & 15
14. 03/01 Network flows and matchings chapter 16-20
15. 03/06 Network flows and matchings chapter 16-20
16. 03/08 --midsemester break--
17. 03/13 Network flows and matchings chapter 16-20
18. 03/15 Linear programming
19. 03/20 Approximation algorithms (LP rounding)
20. 03/22 Entropy and Huffman codes
03/27 --spring break--
03/29 --spring break--
21. 04/03 Approx algs II
22. 04/05 Semidefinite programming
23. 04/10 Random walks, cover times, Markov chains
24. 04/12 Random walks II
25. 04/17 Random walks III
26. 04/19 Random walks IV
27. 04/24 FFT chapter 35
28. 04/26 FFT applications
29. 05/01 Finite fields and polynomials chapter 40
30. 05/03 TBD
Final exam: Thu. May 10 8:30am-11:30am SH 125