6.006: Introduction to Algorithms

1. Introduction
   • Lecture 1, 9/9 Introduction and Document Distance (Handouts: docdist.pdf, docdist7.txt)
     • Recitation 1
   • Lecture 2, 9/14 Peak Finding Problem
2. Binary Search Trees
   • Lecture 3, 9/16 Scheduling and Binary Search Trees
     • Recitation 3
   • Lecture 4, 9/21 Balanced Binary Search Trees
     • Recitation 4
3. Hashing
   • Lecture 5, 9/23 Hashing I : Chaining, Hash Functions
   • Lecture 6, 9/28 Hashing II : Table Doubling, Rolling Hash of Karp and Rabin
     • Recitation 6
   • Lecture 7, 9/30 Hashing III : Open Addressing
4. Sorting
   • Lecture 8, 10/5 Sorting I : Insertion Sort, Merge Sort, Master Theorem
     • Recitation 8 (Handout: Universal Hashing)
   • Lecture 9, 10/7 Sorting II : Heaps
     • Recitation 9 (Handout: Heap Algorithms is just first 2 pages of these notes)
   • Lecture 10, 10/12 Sorting III: Lower Bounds, Counting Sort, Radix Sort
     • Recitation 10: Quiz Practice Problems
   Graphs and Search
   • Lecture 11, 10/14 Searching I: Graph Search and Representations
     • Recitation 11
   • Lecture 12, 10/19 Searching II: Breadth-First Search and Depth-First Search (Powerpoint version:pptx)
     • Recitation 12 (Handout: Search Algorithms is just first 2 pages of these notes)
   • Lecture 13, 10/21 Searching III: Topological Sort (Powerpoint version:pptx)
     • Recitation 13
   • Lecture 14, 10/26 Shortest Paths I: Intro
   • Lecture 15, 10/28 Shortest Paths II: Bellman-Ford
     • Recitation 15
   • Lecture 16, 11/2 Shortest Paths III: Bellman-Ford on DAGs and Dijkstra
   • Lecture 17, 11/4 Shortest Paths IV: Speeding Up Dijkstra (Paper describing these and other speedups to Dijkstra)
     • Recitation 17
5. Dynamic Programming
   • Lecture 18, 11/9 Dynamic Programming I: Memoization, Fibonacci, Crazy Eights
     • Recitation 18
   • Lecture 19, 11/16 Dynamic Programming II: Shortest Paths, Longest Common Subsequence
   • Lecture 20, 11/18 Dynamic Programming III: Dynamic Programming III: Text Justification, Knapsack
     • Recitation 20
   • Lecture 21, 11/23 Dynamic Programming IV: Piano Fingering, Structural DP (Trees), Vertex Cover, Dominating Set, Treewidth
6. Numerics
   • Lecture 22, 11/30 Numerics I
   • Lecture 23, 12/2 Numerics II
     • Recitation 23
7. NP-completeness
   • Lecture 24, 12/7 NP-completeness
8. Review
   • Lecture 25, 12/9 Review.