0
(
ratings
)
5
students
Created by:
![Profile Photo](https://opencoursa.com/wp-content/uploads/avatars/809/62de1041c5027-bpfull.jpg)
Last updated:
December 1, 2022
Duration:
Unlimited Duration
FREE
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
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
1
Reviews
1520
Courses
1916
Students
![Profile Photo](https://opencoursa.com/wp-content/uploads/avatars/809/62de1041c5027-bpfull.jpg)
Massachusetts Institute of Technology