6.006: Introduction to Algorithms

1. Introduction
   • Lecture 1, Introduction and Document Distance (source code and a relevant remark about python. ) Please use nb to jot down any questions you have or improvements you'd like to suggest on the notes; I'll be responding to what's posted there.
   • Recitation 1, Python Introduction and Asymptotic Complexity Review
   • Lecture 2, Peak Finding Problem
   • Recitation 2, Peak Finding Problem
2. Binary Search Trees
   • Lecture 3, Scheduling and Binary Search Trees
   • Recitation 3, Binary Search Trees
   • Lecture 4, Balanced Binary Search Trees
   • Recitation 4, AVL Trees (demo applet)
3. Hashing
   • Lecture 5, Hashing I : Chaining, Hash Functions
   • Recitation 5, Hashing I
   • Lecture 6, Hashing II : Table Doubling, Rolling Hash of Karp and Rabin
   • Recitation 6, Hashing II
   • Lecture 7, Hashing III : Open Addressing
4. Sorting
   • Lecture 8, Sorting I : Insertion Sort, Merge Sort, Master Theorem
   • Lecture 9, Sorting II : Heaps
   • Lecture 10, Sorting III: Lower Bounds, Counting Sort, Radix Sort
5. Graphs and Search
   • Lecture 11, Searching I: Graph Search and Representations
   • Lecture 12, Searching II: Breadth-First Search and Depth-First Search (reading notes)
   • Lecture 13, Searching III: Topological Sort
   • Lecture 14, Shortest Paths I: Intro
   • Lecture 15, Shortest Paths II: Bellman-Ford
   • Lecture 16, Shortest Paths III: Dijkstra and Special Cases
   • Lecture 17, Shortest Paths IV: Speeding Up Dijkstra (and Wagner paper with additional tricks)
6. Dynamic Programming
   • Lecture 18, Dynamic Programming I: Memoization, Fibonacci, Crazy Eights
   • Lecture 19, Dynamic Programming II: Shortest Paths, Longest Common Subsequence, Parent Pointers
   • Lecture 20, Dynamic Programming III: Text Justification, Knapsack, Pseudopolynomial Time
   • Lecture 21, Dynamic Programming IV: Piano Fingering, Structural DP (Trees), Vertex Cover, Dominating Set, Treewidth
7. Numerics
   • Lecture 22, Numerics I
   • Lecture 23, Numerics II
   • Lecture 24, Numerics III
8. NP-completeness
   • Lecture 25, NP-completeness
9. Conclusion
   • Lecture 26