Design and Analysis of Algorithms

1. Course Overview, Interval Scheduling.
2. Divide & Conquer: Convex Hull, Median Finding.
R1. Matrix Multiplication and the Master Theorem.
3. Divide & Conquer: FFT.
R2. 2-3 Trees and B-Trees.
4. Divide & Conquer: van Emde Boas Trees.
5. Amortization: Amortized Analysis.
6. Randomization: Matrix Multiply, Quicksort.
R4. Randomized Select and Randomized Quicksort.
7. Randomization: Skip Lists.
8. Randomization: Universal & Perfect Hashing.
R5. Dynamic Programming.
9. Augmentation: Range Trees.
10. Dynamic Programming: Advanced DP.
11. Dynamic Programming: All-Pairs Shortest Paths.
12. Greedy Algorithms: Minimum Spanning Tree.
R6. Greedy Algorithms.
13. Incremental Improvement: Max Flow, Min Cut.
14. Incremental Improvement: Matching.
R7. Network Flow and Matching.
15. Linear Programming: LP, reductions, Simplex.
16. Complexity: P, NP, NP-completeness, Reductions.
R8. NP-Complete Problems.
17. Complexity: Approximation Algorithms.
18. Complexity: Fixed-Parameter Algorithms.
R9. Approximation Algorithms: Traveling Salesman Problem.
19. Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees.
20. Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees.
R10. Distributed Algorithms.
21. Cryptography: Hash Functions.
22. Cryptography: Encryption.
R11. Cryptography: More Primitives.
23. Cache-Oblivious Algorithms: Medians & Matrices.
24. Cache-Oblivious Algorithms: Searching & Sorting.