# Introduction to Algorithms (SMA 5503)

- 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](https://ocw.mit.edu/courses/6-046j-introduction-to-algorithms-sma-5503-fall-2005/)
- Licence: [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/) (Non-commercial use only.)
- Syllabus: [at the source](https://ocw.mit.edu/courses/6-046j-introduction-to-algorithms-sma-5503-fall-2005/pages/syllabus/)
- Readings: [at the source](https://ocw.mit.edu/courses/6-046j-introduction-to-algorithms-sma-5503-fall-2005/pages/readings/)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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

1. [Lecture 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/82bd5e5eae4f), 1 h 21 min (Video)
2. [Lecture 2: Asymptotic Notation; Recurrences; Substitution, Master Method](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/2f90c2ab3145), 1 h 11 min (Video)
3. [Lecture 3: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/600c52c749d9), 1 h 9 min (Video)
4. [Lecture 4: Quicksort, Randomized Algorithms](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/e1e079c42e47), 1 h 21 min (Video)
5. [Lecture 5: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/9395031f0164), 1 h 17 min (Video)
6. [Lecture 6: Order Statistics, Median](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/0b264fc6bf8e), 1 h 9 min (Video)
7. [Lecture 7: Hashing, Hash Functions](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/b9779e9bfb0a), 1 h 18 min (Video)
8. [Lecture 8: Universal Hashing, Perfect Hashing](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/57a7c798dd44), 1 h 20 min (Video)
9. [Lecture 9: Relation of BSTs to Quicksort - Analysis of Random BST](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/b29b38e35e8a), 1 h 22 min (Video)
10. [Lecture 10: Red-black Trees, Rotations, Insertions, Deletions](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/1bc54fee9007), 1 h 24 min (Video)
11. [Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/f8818792851e), 1 h 24 min (Video)
12. [Lecture 12: Skip Lists](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/cd688b5299a9), 1 h 26 min (Video)
13. [Lecture 13: Amortized Algorithms, Table Doubling, Potential Method](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/511ea1ce8bca), 1 h 20 min (Video)
14. [Lecture 14: Competitive Analysis: Self-organizing Lists](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/fdc8ddab88a7), 1 h 15 min (Video)
15. [Lecture 15: Dynamic Programming, Longest Common Subsequence](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/e9a1c6b3f947), 1 h 12 min (Video)
16. [Lecture 16: Greedy Algorithms, Minimum Spanning Trees](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ba48b38aef59), 1 h 25 min (Video)
17. [Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/0dd2f3ee51b8), 1 h 25 min (Video)
18. [Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/c22db2289acb), 1 h 18 min (Video)
19. [Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/af26d2e6ce36), 1 h 16 min (Video)
20. [Lecture 22: Advanced Topics](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/d39edb1f1fda), 1 h 16 min (Video)
21. [Lecture 23: Advanced Topics (cont.)](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/a91c6dc66066), 1 h 17 min (Video)
22. [Lecture 24: Advanced Topics (cont.)](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/885f345e81f6), 1 h 25 min (Video)
23. [Lecture 25: Advanced Topics (cont.) - Discussion of Follow-on Classes](https://invisiblenetwork.ai/learn/mit/6-046j-introduction-to-algorithms-sma-5503-fall-2005/d67dbb73630f), 1 h 26 min (Video)