Design and Analysis of Algorithms
Offered By: Massachusetts Institute of Technology via MIT OpenCourseWare
Course Description
Overview
Syllabus
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.
Taught by
MIT OpenCourseWare
Tags
Related Courses
The Next Generation of InfrastructureDelft University of Technology via edX The Beauty and Joy of Computing - AP® CS Principles Part 2
University of California, Berkeley via edX Advanced Data Structures in Java
University of California, San Diego via Coursera Theory of Computation
Indian Institute of Technology Kanpur via Swayam 离散数学
Shanghai Jiao Tong University via Coursera