Catalog

Design and Analysis of Algorithms

Electrical Engineering and Computer Science MIT CC BY-NC-SA 4.0 34 lectures

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.

Syllabus

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

Course materials