Home

Course Information

Calendar

Piazza

Lectures

Problem Sets

Quizzes

Resources

Previous terms

6.006: Introduction to Algorithms

1. Introduction
   • Lecture 1, 2/7 Introduction and Document Distance (Handouts: docdist python sourcecode, documents)
   • Lecture 2, 2/9 Peak Finding Problem
2. Binary Search Trees
   • Lecture 3, 2/14 Scheduling and Binary Search Trees and in pdf without animations. Readings: 10.4, 12.1, 12.2, 12.3
   • Lecture 4, 2/16 Balanced Binary Search Trees, Readings: 13.2, 14
3. Hashing, Readings: 11.1-11.3, 17, 11.4
   • Lecture 5, 2/23 Hashing I : Chaining, Hash Functions.
   • Lecture 6, 2/28 Hashing II : Table Doubling, Rolling Hash (of Karp and Rabin)
   • Lecture 7, 3/1 Hashing III : Open Addressing
4. Sorting, Readings: Chapter 4, 2.1, 2.2, 2.3, 6.1, 6.2, 6.3 and 6.4, 8.1-8.4
   • Lecture 8, 3/6 Sorting I : Insertion Sort, Merge Sort, Master Theorem.
   • Lecture 9, 3/8 Sorting II : Heaps and Heapsort
   • Lecture 10, 3/13 Sorting III : Lower Bounds, Counting Sort, Radix Sort
5. Graphs and Search, Readings: 22.1-22.3, B.4
   • Lecture 11, 3/15 Searching I: Graph Search and Representations.
   • Lecture 12, 3/20 Searching II: Breadth-First Search and Depth-First Search.
   • Lecture 13, 3/22, Searching III: Connected Components, Topological Sort, See CLRS: 22.4-22.5.
   • Lecture 14, 4/3 Shortest Paths I: Intro, Dijstra's Algorithm
   • Lecture 15, 4/5 Shortest Paths II: Bellman-Ford
   • Lecture 16, 4/10 Shortest Paths III: Bellman-Ford on DAGs and Dijkstra
   • Lecture 17, 4/12 Shortest Paths IV: Speeding Up Dijkstra
6. Dynamic Programming
   • Lecture 18, 4/19 Dynamic Programming I: Memoization, Fibonacci, Crazy Eights
   • Lecture 19, 4/24 Dynamic Programming II: All-Pairs Shortest Paths, Longest Common Subsequence
   • Lecture 20, 4/26 Dynamic Programming III: Bottom-up Implementation, Knapsack
   • Lecture 21, 5/1 Dynamic Programming IV: Text Justification, Structural DP (on Trees), Vertex Cover, Maximum Parsimony
7. Number Theory
   • Lecture 22, 5/3 Number Theory
   • Lecture 23, 5/8 Number Theory Continued
8. NP-Completeness
   • Lecture 24, 5/10 NP Completeness
9. Other Topics
   • Lecture 25, 5/15 Primality Testing
   • Lecture 26, 5/17 Randomized Algorithms: Min-Cut; Random Walks; Markov Chains
PDF LECTURES