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