Calendar

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