Created by:

Profile Photo

Last updated:

December 1, 2022


Unlimited Duration


This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration


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 Singapore-MIT Alliance (SMA) programme as course number SMA 5503 (Analysis and Design of Algorithms).

Course Curriculum

  • Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort Unlimited
  • Asymptotic Notation; Recurrences; Substitution, Master Method Unlimited
  • Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication Unlimited
  • Quicksort, Randomized Algorithms Unlimited
  • Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort Unlimited
  • Order Statistics, Median Unlimited
  • Hashing, Hash Functions Unlimited
  • Universal Hashing, Perfect Hashing Unlimited
  • Relation of BSTs to Quicksort – Analysis of Random BST Unlimited
  • Red-black Trees, Rotations, Insertions, Deletions Unlimited
  • Augmenting Data Structures, Dynamic Order Statistics, Interval Trees Unlimited
  • Skip Lists Unlimited
  • Amortized Algorithms, Table Doubling, Potential Method Unlimited
  • Competitive Analysis: Self-organizing Lists Unlimited
  • Dynamic Programming, Longest Common Subsequence Unlimited
  • Greedy Algorithms, Minimum Spanning Trees Unlimited
  • Shortest Paths I: Properties, Dijkstra’s Algorithm, Breadth-first Search Unlimited
  • Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints Unlimited
  • Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson Unlimited
  • Advanced Topics Unlimited
  • Advanced Topics (cont.) Unlimited
  • Advanced Topics (cont.) – Discussion of Follow-on Classes Unlimited

About the instructor

5 5

Instructor Rating







Profile Photo
Massachusetts Institute of Technology