Home Page: Graduate Algorithms, Spring 2001 (original) (raw)

| | TimeLocation | TR 1:00PM-2:20PMWean 4615A | | | | | ------------------ | ------------------------------------------------------------------------------------------------------------------------------------------ | -------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------- | | | Instructors | Avrim Blum[avrim | Wean 4107 | 8-6452] Office hours: Tues 2:30 | Danny Sleator[sleator | Wean 4111 | 8-7563] Office hours: tbd | | | Secretary | Dorothy Zaborowski [daz | Wean 4116 | 8-3779] | | | | | Textbook | Kozen, "The Design and Analysis of Algorithms" (Springer). Also see: Motwani & Raghavan, "Randomized Algorithms" (Cambridge). | | | |

Final exam: Thu. May 10 8:30am-11:30am SH 125

Course information:

• Course schedule (includes recommended readings).
• Grading policy.

Handouts:

• Background reading (15-451 lectures 1-5).
• Karger-Klein-Tarjan MST paper.
• Last year's final

Assignments:

• Assignment 1. Solutions.
• Assignment 2. Hints and More Hints.Solutions.
• Assignment 3. (due 02/27/01)Solutions.
• Assignment 4. (due 03/06/01)Solutions.
• Assignment 5.Solutions.
• Assignment 6.Solutions.
• Assignment 7. (due 05/01/01)

Lecture notes:

1. 01/16: Karatsuba, Strassen, probability, quicksort [see also background handout]
2. 01/18: Binary search trees and Treaps. [Kozen 13]
3. 01/23: amortized analysis and Splay trees. [Kozen 12]
4. 01/25: Splay trees continued
5. 01/30: Topological sorting, MST: Prim & Kruskal. [Kozen 2,4]
6. 02/01: Union-find. [Kozen 10]
7. 02/06: Fibonacci heaps. [Kozen 8,9]
8. 02/08: Linear time randomized MST. See [KKT] paper.
9. 02/13: Randomized global min cuts.
10. 02/15: Voronoi Diagrams and Delaunay Triangulations
11. 02/20: Point location using persistent search trees
12. 02/22: Point location: Seidel
13. 02/27: The Planar Separator Theorem [Kozen 15]
14. 03/01: Max flow I: Ford-Fulkerson, Edmonds-Karp #1. [Kozen 16,17]
15. 03/06: Max flow II: Edmonds-Karp #2, MPM, app to image processing. [Kozen 17,18]
16. 03/13: Min-cost Max flow, min-cost circulation, Goldberg-Tarjan. See also Michel Goemans's notes.
17. 03/15: Linear programming.
18. 03/20: Approximation algorithms(Vertex cover, Set cover). Notes on randomized routing.
19. 03/22: Data Compression and Huffman codes
20. 04/03: Approx algs II: the probabilistic method, randomized rounding and MAX-SAT
21. 04/05: Approx algs III: Semidefinite Programming for MAX-Cut, MAX-2SAT.
22. 04/10: Random walks I: Hitting time, cover time, etc. Here is a survey paper by Lovasz.
23. 04/12: Random walks II: rapid mixing. See this paper by Mark Jerrum
24. 04/17: Random walks III: coupling, random k-coloring contd.
25. 04/19: Random walks IV: line coupling, eigenvalue gaps, conductance and expansion. See also this nice survey by Jerrum and Sinclair.
26. 04/24: FFT.
27. 04/26: FFT applications. No notes.
28. 05/01: Finite Fields and their applications.