Instructor: Erik Demaine

In this lecture, Professor Demaine covers different algorithmic solutions for the All-Pairs Shortest Paths problem.

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

This is an intermediate algorithms course with an emphasis on teaching techniques for the design and analysis of efficient algorithms, emphasizing methods of application. Topics include divide-and-conquer, randomization, dynamic programming, greedy algorithms, incremental improvement, complexity, and cryptography.

This course is taught by Prof. Erik Demaine, Prof. Srinivas Devadas, and Prof. Nancy Lynch.