Design and Analysis of Algorithms (M-I-T)

• 1. Course Overview, Interval Scheduling (M-I-T)
• 2. Divide & Conquer: Convex Hull, Median Finding (M-I-T)
• R1. Matrix Multiplication and the Master Theorem (M-I-T)
• 3. Divide & Conquer: FFT (M-I-T)
• R2. 2-3 Trees and B-Trees (M-I-T)
• 4. Divide & Conquer: van Emde Boas Trees (M-I-T)
• 5. Amortization: Amortized Analysis (M-I-T)
• 6. Randomization: Matrix Multiply, Quicksort (M-I-T)
• R4. Randomized Select and Randomized Quicksort (M-I-T)
• 7. Randomization: Skip Lists (M-I-T)
• 8. Randomization: Universal & Perfect Hashing (M-I-T)
• R5. Dynamic Programming (M-I-T)
• 9. Augmentation: Range Trees (M-I-T)
• 10. Dynamic Programming: Advanced DP (M-I-T)
• 11. Dynamic Programming: All-Pairs Shortest Paths (M-I-T)
• 12. Greedy Algorithms: Minimum Spanning Tree (M-I-T)
• R6. Greedy Algorithms (M-I-T)
• 13. Incremental Improvement: Max Flow, Min Cut (M-I-T)
• 14. Incremental Improvement: Matching (M-I-T)
• 15. Linear Programming: LP, reductions, Simplex (M-I-T)
• 16. Complexity: P, NP, NP-completeness, Reductions (M-I-T)
• R8. NP-Complete Problems (M-I-T)
• 17. Complexity: Approximation Algorithms (M-I-T)
• 18. Complexity: Fixed-Parameter Algorithms (M-I-T)
• R9. Approximation Algorithms: Traveling Salesman Problem (M-I-T)