5
This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice.
FREE
This course includes
Hours of videos
611 years
Units & Quizzes
22
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
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 Currilcum
- 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
