Education For All

www.edforall.net

Text size
  • Increase font size
  • Default font size
  • Decrease font size

Introduction to Algorithms

Course Summary

This course is based on 6.046J Introduction to Algorithms made available by Massachusetts Institute of Technology: MIT OpenCourseWare under the Creative Commons BY-NC-SA license.
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.

(8 Oct 2011 - Updated)

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.

ASSIGNMENTS SOLUTIONS
Problem Set 1 PDF) PDF)
Problem Set 2 (PDF) (PDF)
Problem Set 3 (PDF) (PDF)
Problem Set 4 (PDF) (PDF)
Problem Set 5 (PDF) PDF)
Problem Set 6 (PDF) PDF)
Problem Set 7 (PDF)

Sample Input, sample.txt (TXT)
Sample Output, samplesol.txt (TXT)
Input 1, input1.txt (TXT)
Input 2, input2.txt (TXT)
Input 3, input3.txt (TXT)
(PDF)

Source Code, editDistance.java (JAVA)
Source Code, editDistance.c (C)
Problem Set 8 (PDF) (PDF)
Problem Set 9 (PDF) (PDF)

2. Exam questions and solutions
Quiz and exam questions together with the solutions are available here.

EXAMS SOLUTIONS
Practice Quiz 1 (PDF) PDF)
Practice Quiz 2 (PDF)  
Practice Final Exam (PDF) (PDF)
Quiz 1 (PDF) (PDF)
Quiz 2 (PDF) (PDF)
Final Exam (PDF) (PDF)

Other Resources

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.


 

Translate

Chinese (Simplified) French German Italian Japanese Korean Portuguese Russian Spanish
More educational resources: