| SES # | TOPICS | KEY DATES |
|---|---|---|
| Introduction and document distance | ||
| L1 | Introduction and document distance | |
| R1 | Document distance in Python (docdist{1,2,3,4}.py) | |
| L2 | More document distance, mergesort | |
| R2 | Python cost model, review for asymptotic notation and mergesort | |
| Binary search trees | ||
| L3 | Airplane scheduling, binary search trees | |
| R3 | Binary search trees | |
| L4 | Balanced binary search trees | |
| R4 | AVL Trees (balanced binary search trees) | |
| Hashing | ||
| L5 | Hashing I: chaining, hash functions | Problem set 1 due |
| R5 | Hashing in Python, mutability | |
| L6 | Hashing II: table doubling, Karp-Rabin | |
| R6 | Karp-Rabin review, rolling hashes principles and code | |
| L7 | Hashing III: open addressing | |
| R7 | Open addressing: theory review, Python code More rolling hashes | |
| Sorting | ||
| L8 | Sorting I: heaps | |
| R8 | Overview of sorting methods Heaps as data structures: principles, sorting, priority queues | |
| L9 | Sorting II: heaps | Problem set 2 due |
| L10 | Sorting III: lower bounds, linear-time sorting | |
| R9 | Quiz review: interesting problems | Quiz 1 |
| L11 | Sorting IV: stable sorting, radix sort | |
| R10 | Counting, radix and bucket sorting, gas simulation | |
| Searching | ||
| L12 | Searching I: graph search, representations, and applications | |
| L13 | Searching II: breadth-first search and depth-first search | Problem set 3 due |
| L14 | Searching III: topological sort and NP-completeness | |
| R11 | Breadth-first search and depth-first search | |
| Shortest paths | ||
| L15 | Shortest paths I: intro | |
| R12 | Assistance for problem set | |
| L16 | Shortest paths II: Bellman-Ford | Problem set 4 due |
| R13 | Generic shortest-path algorithm: concepts, properties Bellman-Ford: examples, negative-cost cycles | |
| L17 | Shortest paths III: Dijkstra | |
| R14 | Hands-on Dijkstra: pseudocode, preconditions, examples, why it works Priority queues: review, extended Python implementation | |
| L18 | Shortest paths IV: Dijkstra speedups | |
| R15 | Array implementation of Dijkstra | Quiz 2 |
| Dynamic programming | ||
| L19 | Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing | |
| R16 | Hands-on dynamic programming: big ideas, memoization in Fibonacci, crazy cards, Dijkstra and Bellman-Ford algorithm as dynamic programming | |
| L20 | Dynamic programming II: longest common subsequence (LCS), parent pointers | |
| R17 | More dynamic programming: beating Super Mario Brothers, getting points back on tests (LCS), Crazy Eights | |
| L21 | Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris training | Problem set 5 due |
| R18 | Even more dynamic programming: maximum-sum sub-array, more Tetris | |
| L22 | Dynamic programming IV: piano fingering, structural DP (trees), vertex cover, dominating set, and beyond | |
| R19 | Knapsack and its variants, structural dynamic programming: covering a tree with templates, dominating set | |
| Numerics | ||
| L23 | Numerics I | |
| R20 | Dynamic programming practice: live Python coding, dominating sets, structural dynamic programming: covering a tree with templates | |
| L24 | Numerics II | Problem set 6 due |
| R21 | Divide and conquer vs. dynamic programming on problems: matrix multiplication, tower, max-sum subarray, closest pair | |
| R22 | Numerics review, Strassen's algorithm for matrix multiplication | |
| Beyond 6.006 | ||
| L25 | Beyond 6.006: follow-on classes, geometric folding algorithms | |
| R23 | Review for the final exam | |