CMU       15-451       Spring 2006

Instructor: Danny Sleator

TAs: Daniel Golovin, Lea Kissner


Announcements

Hot off the press:

Older stuff:


General info


Minis


Homeworks


Lecture notes

  1. 01/17:Intro & Admin. Karatsuba/Strassen. [ps,pdf]
  2. 01/19: Asymptotic analysis, solving recurrences (See notes of 01/17).
  3. 01/24: Probabilistic Analysis, Quicksort (See notes of 01/17).
  4. 01/26: Selection (See notes of 01/17).
  5. 01/31: Soring Lower Bounds (See notes of 01/17).
  6. 02/02: Red-Black Trees [txt].
  7. 02/07: Amortized Analysis [ps,pdf]   Growing and Shrinking a Table [txt].
  8. 02/09: Splay Trees [txt].   Advanced Splay Tree Analysis [txt].
  9. 02/14: Radix Structures [pdf].   The World's Fastest Scrabble Program [pdf].
  10. 02/16: Hashing (see 13.6 of the book)
  11. 02/21: Dynamic Programming (chapter 6 of the book)
  12. 02/23: Dynamic Programming contd (chapter 6 of the book)
  13. 02/28: Bellman Ford shortest path algorithm (6.8 and 6.10)
  14. 03/02: Depth First Search and Strong Components [DFS Background (txt)] [Strong Components (pdf)]
  15. 03/07: BFS, Dijkstra, Minimum Spanning Trees [txt]
  16. 03/09: Midterm Exam (Here it is: [ps])
  17. 03/21: Network Flows and Matchings I (7.1-7.3 and 7.5-7.6)
  18. 03/23: Network Flows and Matchings I (7.7-7.11)
  19. 03/28: Two Algorithms for Finding Closest Pairs (13.7 and 5.4)
  20. 03/30: Voronoi Diagrams, Point Location, and Persistence [pdf]
  21. 04/04: FFT (5.6)
  22. 04/06: Competitive Algorithms (deterministic) [txt]    Migration Problems [pdf]
  23. 04/11: Competitive Algorithms (randomized) [txt]
  24. 04/13: Linear Programming [txt]
  25. 04/18: random problems
  26. 04/25: NP-completeness I [pdf]
  27. 04/27: NP-completeness II [pdf]
  28. 05/02: Approximation Algorithms I (chapter 11.1 and [txt])
  29. 05/04: Approximation Algorithms II (chapter 13.4)