These recitation slides are courtesy of Victor Costan, one of the course TAs, and are used with permission.
REC # | TOPICS | SUPPORTING FILES |
---|---|---|
Introduction and document distance | ||
R1 | Document distance in Python (docdist{1,2,3,4}.py) (PDF) | |
R2 | Python cost model, review for asymptotic notation and mergesort (PDF) |
Zipped data (numbers) (ZIP) (This zip file includes: 2 .jpg files, 1 .gz file, 1 .tiff file, 1 .numbers file, and 1 .pkginfo file.) Python Cost Model |
Binary search trees | ||
R3 | Binary search trees (PDF) | Code for binary search trees augmented with subtree size (PY) |
R4 | AVL Trees (balanced binary search trees) (PDF) | Code for AVL trees (uses the BST code from R3) (PY) |
Hashing | ||
R5 | Hashing in Python, mutability (PDF) | The dangers of mutable dictionary keys (PY) |
R6 | Karp-Rabin review, rolling hashes principles and code (PDF) | Rolling hash code (PY) |
R7 |
Open addressing: theory review, Python code More rolling hashes (PDF) |
Open addressing code (PY) |
Sorting | ||
R8 |
Overview of sorting methods Heaps as data structures: principles, sorting, priority queues (PDF) |
|
R9 | Quiz review: interesting problems (PDF) | |
R10 | Counting, radix and bucket sorting, gas simulation | |
Searching | ||
R11 | Breadth-first search and depth-first search (PDF) |
Code for breadth-first search (PY) Code for depth-first search (PY) |
Shortest paths | ||
R12 | Assistance for problem set (PDF) | |
R13 |
Generic shortest-path algorithm: concepts, properties Bellman-Ford: examples, negative-cost cycles |
|
R14 |
Hands-on Dijkstra: pseudocode, preconditions, examples, why it works Priority queues: review, extended Python implementation (PDF) |
|
R15 | Array implementation of Dijkstra | |
Dynamic programming | ||
R16 | Hands-on dynamic programming: big ideas, memoization in Fibonacci, crazy cards, Dijkstra and Bellman-Ford algorithm as dynamic programming (PDF) | |
R17 | More dynamic programming: beating Super Mario Brothers, getting points back on tests (LCS), Crazy Eights (PDF) | |
R18 | Even more dynamic programming: maximum-sum sub-array, more Tetris (PDF) | |
R19 | Knapsack and its variants, structural dynamic programming: covering a tree with templates, dominating set | |
Numerics | ||
R20 | Dynamic programming practice: live Python coding, dominating sets, structural dynamic programming: covering a tree with templates |
Live Python Coding problems (problem statement, tests, and solutions are included): - Matrix chain multiplication (ZIP) (This zip file includes: 3 .py files, 1 .pyc file, 1 .rb file, and 6 data files.) - Longest zig-zag subsequence (ZIP) (This zip file includes: 3 .py files, 1 .pyc file, 1 .rb file, and 4 data files.) |
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 | Strassen's algorithm for fast matrix multiplication is covered in CRLS, chapter 28, pp. 735-742. |
Beyond 6.006 | ||
R23 | Review for the final exam (PDF) |