Syllabus

Here is my course syllabus: [pdf]. As noted, this is only a rough guideline, and it might change depending on how each lecture progresses.

  1. Introduction/Recurrences. [slides]
  2. Recurrences/Divide & Conquer: Karatsuba, Strassen. [L2] (Slides are not annotated due to Jarnal crash.)
  3. Divide & Conquer (DC): Selection, closest pair, van emde Boas queues. [L3]
  4. DC: van emde Boas queues, Fast Fourier Transform. [L4]
  5. DC: Fast Fourier Transform, Dynamic Programming (DP)[L5]
  6. DP: Posters, Matrix Chain Multiplication [L6] (Slides are not annotated due to Jarnal crash.)
  7. DP: Typesetting, Seam Carving, Gerrymandering [L7]
  8. Greedy: Scheduling, Huffman [L8]
  9. Graphs: MST, Prim, Kruskal [L9]
  10. Amortized Analysis, Binary counter, Fibonacci Heaps [L10]
  11. Sarita Adve Lecture
  12. Fibonnaci heaps, shortest paths [L12]
  13. Shortest paths: Dijkstra, BellmanFord; All-pairs shortest paths: Floyd-Warshall, Johnson [L13]
  14. Sofya Raskhodnikova Lecture: Transitive-closure Spanners [Her Slides]
  15. Adam Smith Lecture: Pinning Down “Privacy” in Statistical Databases
  16. Max-flow/min-cut, Ford-Fulkerson [L16]
  17. Max-flow: Edmonds-Karp, Push-Relabel [L17]
  18. Push-Relabel [L18]
  19. Scott Aaronson lecture: The Limits of Quantum Computing
  20. Applications of Max-flow [L20]
  21. Vertex-disjoint paths, Baseball elimination [L21]
  22. Linear Programming [L22]
  23. Simplex, Duality, Zero-Sum Games [L23]
  24. Zero-Sum Games, Correlated Equilibria [L24]
  25. Correlated Equilibria, Randomized Algorithms [L25]
  26. Randomized Algorithms: Global mincut, Solitaire, Freivald [L26]
  27. Randomized Algorithms: Freivald, Selection, String matching [L27 (not annotated)]
  28. Vertex Cover Approx, Set-cover approx [L28]