This table provides information about both the lecture (L) and recitation (R) sessions.
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 |