These lectures are primiarly based on your textbook, Algorithm Design, by Kleinberg and Tardos. The slides are accessible only from computers on a UMD network or via VPN.

1. Introduction & Stable Matching (9/2)
2. Analysis Basics (9/4)
3. Graphs & Basic Graph Algorithms (9/9)
4. Interval Scheduling & Interval Partitioning (9/11)
5. Scheduling to Minimize Lateness (9/16)
6. Optimal Caching & Fractional Knapsack
   Dijkstra's algorithm (9/18)
7. Minimum Spanning Trees & Clustering (9/23)
8. Divide & Conquer - MergeSort, Counting Inversions (9/25)
9. Finding Closest Points (9/30)
10. Dynamic Programming & Weighted Interval Scheduling (10/2)
11. Subset Sum & Knapsack (10/7)
12. RNA Folding (10/9)
13. Sequence Alignment (10/14)
14. Midterm #1 (10/16)
15. Bellman-Ford (10/21)
16. Network Flow, Max-Flow=Min-Cut (10/23 & 10/28)
17. Maximum Bipartite Matching (10/28)
18. Guest Lecture: Advanced Dynamic Programming (10/30)
19. Guest Lecture: Choosing Good Augmenting Paths (11/4)
20. Image Segmentation (11/6)
21. Extensions to Max Flow, Survey Design (11/11)
22. Disjoint paths, linear programming (11/13)
23. The class NP (11/18)
24. Polynomial-time reductions & NP-completeness (11/20)
25. More NP-completeness results (11/25)
26. NP-completeness: 3-dimensional matching & subset sum (12/2)
27. Midterm #2 (12/4)
28. Approximation algorithms: Vertex Cover, Minimum Makespan, TSP
29. Local search, randomized algorithms

↩ Return to main class page