MIT 6.046J Design and Analysis of Algorithms, Spring 2015

2. Divide & Conquer: Convex Hull, Median Finding

24. Cache-Oblivious Algorithms: Searching & Sorting

7. Randomization: Skip Lists

R2. 2-3 Trees and B-Trees

14. Incremental Improvement: Matching

R10. Distributed Algorithms

15. Linear Programming: LP, reductions, Simplex

R6. Greedy Algorithms

1. Course Overview, Interval Scheduling

10. Dynamic Programming: Advanced DP

13. Incremental Improvement: Max Flow, Min Cut

4. Divide & Conquer: van Emde Boas Trees

21. Cryptography: Hash Functions

R9. Approximation Algorithms: Traveling Salesman Problem

12. Greedy Algorithms: Minimum Spanning Tree

3. Divide & Conquer: FFT

R11. Cryptography: More Primitives

22. Cryptography: Encryption

20. Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees

R7. Network Flow and Matching

R4. Randomized Select and Randomized Quicksort

6. Randomization: Matrix Multiply, Quicksort

9. Augmentation: Range Trees

8. Randomization: Universal & Perfect Hashing

R1. Matrix Multiplication and the Master Theorem

11. Dynamic Programming: All-Pairs Shortest Paths

R8. NP-Complete Problems

17. Complexity: Approximation Algorithms

19. Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees

R5. Dynamic Programming

5. Amortization: Amortized Analysis

18. Complexity: Fixed-Parameter Algorithms

16. Complexity: P, NP, NP-completeness, Reductions

23. Cache-Oblivious Algorithms: Medians & Matrices