UNIVERSITY GRADUATE COURSES IN COMPUTER SCIENCE
15-750: GRADUATE ALGORITHMS, SPRING 2001
Avrim Blum, Daniel Sleator

   Time
Location
TR 1:00PM-2:20PM
Wean 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:

Handouts:

Assignments:

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.