0

(

ratings

)

5

students

Created by:

Profile Photo

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

1915

Students

Profile Photo
Massachusetts Institute of Technology