| LEC # | TOPICS | SUPPORTING FILES |
|---|---|---|
| Introduction and document distance | ||
| L1 | Introduction and document distance (PDF) | Document distance (docdist{1,2,3,4}.py) |
| L2 | More document distance, mergesort (PDF) | Document distance (docdist{5,6}.py) |
| Binary search trees | ||
| L3 | Airplane scheduling, binary search trees (PDF - 1.4 MB) | Binary search trees (including code) |
| L4 | Balanced binary search trees (PDF - 1.4 MB) | See binary search trees for AVL code |
| Hashing | ||
| L5 | Hashing I: chaining, hash functions (PDF) | Document distance (docdist-dict.py) |
| L6 | Hashing II: table doubling, Karp-Rabin (PDF) | |
| L7 | Hashing III: open addressing (PDF - 1.1 MB) | |
| Sorting | ||
| L8 | Sorting I: heaps (PDF - 1.0 MB) | |
| L9 | Sorting II: heaps (PDF) | |
| L10 | Sorting III: lower bounds, linear-time sorting (PDF) | |
| L11 | Sorting IV: stable sorting, radix sort (PDF - 1.0 MB) | |
| Searching | ||
| L12 | Searching I: graph search, representations, and applications (PDF - 1.6 MB) | Simple Python code for graphs (PY) |
| L13 | Searching II: breadth-first search and depth-first search (PDF - 1.3 MB) | |
| L14 | Searching III: topological sort and NP-completeness (PDF) | |
| Shortest paths | ||
| L15 | Shortest paths I: intro (PDF - 1.0 MB) | |
| L16 | Shortest paths II: Bellman-Ford (PDF - 1.1 MB) | |
| L17 | Shortest paths III: Dijkstra (PDF) | |
| L18 | Shortest paths IV: Dijkstra speedups (PDF - 1.2 MB) | |
| Dynamic programming | ||
| L19 | Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing (PDF) | |
| L20 | Dynamic programming II: longest common subsequence, parent pointers (PDF) | |
| L21 | Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris training (PDF) | |
| L22 | Dynamic programming IV: piano fingering, structural DP (trees), vertex cover, dominating set, and beyond (PDF) | |
| Numerics | ||
| L23 | Numerics I (PDF) | Demos: square root of 2, chord length Source code (ZIP) (This zip file includes: 14 .js files, 2 .html files, 1 .css file, and 1 .project file.) |
| L24 | Numerics II (PDF) | |
| Beyond 6.006 | ||
| L25 | Beyond 6.006: follow-on classes, geometric folding algorithms (PDF) | If you are interested in folding algorithms, you can look at the previous offering of 6.885 and the associated textbook. |