Catalog

Introduction to Algorithms (SMA 5503)

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

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing. This course was also taught as part of the {{% resource_link "36e80238-3ea0-4af0-a9c1-59a0d8890e46" "Singapore-MIT Alliance" %}} (SMA) programme as course number SMA 5503 (Analysis and Design of Algorithms).

Syllabus

  1. 1 Lecture 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort
  2. 2 Lecture 2: Asymptotic Notation; Recurrences; Substitution, Master Method
  3. 3 Lecture 3: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication
  4. 4 Lecture 4: Quicksort, Randomized Algorithms
  5. 5 Lecture 5: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort
  6. 6 Lecture 6: Order Statistics, Median
  7. 7 Lecture 7: Hashing, Hash Functions
  8. 8 Lecture 8: Universal Hashing, Perfect Hashing
  9. 9 Lecture 9: Relation of BSTs to Quicksort - Analysis of Random BST
  10. 10 Lecture 10: Red-black Trees, Rotations, Insertions, Deletions
  11. 11 Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees
  12. 12 Lecture 12: Skip Lists
  13. 13 Lecture 13: Amortized Algorithms, Table Doubling, Potential Method
  14. 14 Lecture 14: Competitive Analysis: Self-organizing Lists
  15. 15 Lecture 15: Dynamic Programming, Longest Common Subsequence
  16. 16 Lecture 16: Greedy Algorithms, Minimum Spanning Trees
  17. 17 Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
  18. 18 Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints
  19. 19 Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson
  20. 20 Lecture 22: Advanced Topics
  21. 21 Lecture 23: Advanced Topics (cont.)
  22. 22 Lecture 24: Advanced Topics (cont.)
  23. 23 Lecture 25: Advanced Topics (cont.) - Discussion of Follow-on Classes

Course materials