Education For All

Lectures (Video)

Introduction to Algorithms

Course Summary

This course is taught at MIT by Prof. Erik Demaine and Prof. Charles Leiserson. Prof. Leiserson co-authored the textbook for the course Introduction to Algorithms, Second Edition. 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. A full set of lecture notes is available together with this course.

Reading Material

1. Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 2nd Edition, MIT Press, 2001, ISBN 0262032937, 9780262032933.
(Click the button below to see a preview of the book)


(Click the image below for the link to 3rd edition of the book)

Course Material

1. Assignments
Problems sets and solutions.
2. Exam questions and solutions
Quiz and exam questions together with the solutions are available here.

Other Resources

Lecture notes from MIT Course 6.006, Spring 2008

1. Document distance
Introduction and document distance
2. Mergesort
Mergesort
3. Binary search trees (1.4 MB)
Airplane scheduling, binary search trees
4. Balanced binary search trees (1.2 MB)
Balanced binary search trees
5. Hashing I
Hashing I: chaining, hash functions
6. Hashing II
Hashing II: table doubling, Karp-Rabin
7. Hashing III
Hashing III: open addressing
8. Sorting I (1 MB)
Sorting I: heaps
9. Sorting II
Sorting II: heaps
10. Sorting III
Sorting III: lower bounds, linear-time sorting
11. Sorting IV (1 MB)
Sorting IV: stable sorting, radix sort
12. Searching I (1.6 MB)
Searching I: graph search, representations, and applications
13. Searching II (1.3 MB)
Searching II: breadth-first search and depth-first search
14. Searching III
Searching III: topological sort and NP-completeness
15. Shortest paths I
Shortest paths I: intro
16. Shortest paths II (1.1 MB)
Shortest paths II: Bellman-Ford
17. Shortest paths III
Shortest paths III: Dijkstra
18. Shortest paths IV (1.2 MB)
Shortest paths IV: Dijkstra speedups
19. Dynamic programming I
Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing
20. Dynamic programming II
Dynamic programming II: longest common subsequence, parent pointers
21. Dynamic programming III
Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris training
22. Dynamic programming IV
Dynamic programming IV: piano fingering, structural DP (trees), vertex cover, dominating set, and beyond
23. Numerics I
Numerics I
24. Numerics II
Numerics II
25. Geometric folding algorithms
Beyond 6.006: follow-on classes, geometric folding algorithms

Software

Not available.

Discussion Forum

For discussion on this topic, please go to the relevant forum for Introduction to Algorithms. Click the button below to open the forum page in a new window.