Learn · MIT OpenCourseWare

Cover of the textbook used in this course.

Course6.046J / 18.410J23 lectures30 h 7 min

Introduction to Algorithms (SMA 5503)

Prof. Charles Leiserson and Prof. Erik Demaine · Massachusetts Institute of Technology

Start with lecture 1 At MIT OpenCourseWare

About

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).

Lectures

Video Lectures

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

Syllabus and materials

At MIT OpenCourseWare, as the course publishes them.

Credits and licence

Institution
Massachusetts Institute of Technology
Department
Electrical Engineering and Computer Science; Mathematics
Taught by
Prof. Charles Leiserson, Prof. Erik Demaine
Term
Fall 2005
Level
Undergraduate
Language
English
Subjects
Mathematics, Computer science, Engineering
Source
MIT OpenCourseWare
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only. MIT OpenCourseWare's terms
Attribution
Prof. Charles Leiserson, Prof. Erik Demaine. Introduction to Algorithms (SMA 5503). Fall 2005. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu/. License: Creative Commons BY-NC-SA.
Who can watch
MIT OpenCourseWare gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed