CMSC 451: Lecture Slides

These lectures are primarily based on your textbook, Algorithm Design, by Kleinberg and Tardos.

  1. Introduction and Stable Marriage
  2. Basic Algorithm Analysis
  3. Basic Graph Algorithms
  4. Interval Scheduling and Partitioning
  5. Scheduling to Minimize Lateness
  6. Optimal Caching
  7. Dijkstra's Algorithm
  8. Minimum Spanning Trees & Clustering
  9. Matroids
    Unedited Lecture Notes on Matroids (UMD only)
  10. Counting Inversions
  11. Finding Closest Pair of Points
  12. Dynamic Programming
  13. Subset Sum & Knapsack
  14. Sequence Alignment
  15. RNA Folding
  16. Shortest Paths in Graphs
  17. Network Flows
  18. Bipartite Matching
  19. Edge-disjoint Paths
  20. Image Segmentation
  21. Extensions to Network Flows
  22. Linear Programming
    Draft Manual on using MathProg for ILP (UMD only)
  23. P and NP
  24. NP-completeness
  25. SAT, Coloring, TSP
  26. 3-dimensional matching, Subset Sum
  27. Approximation Algorithms
  28. Randomized Algorithms

You can download all the slides as a single PDF here