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.
- 04/24: FFT.
- 04/26: FFT applications. No notes.
- 05/01: Finite Fields and their applications.
You Might Also Like
If you enjoyed this article, please consider sharing it!
