|
Introduction and document distance
|
|
|
|
L1
|
Introduction and document distance
|
CLRS, chapters 1-3
|
|
L2
|
More document distance, mergesort
|
CLRS, sections 11.1-11.2
|
|
Binary search trees
|
|
|
|
L3
|
Airplane scheduling, binary search trees
|
CLRS, chapter 10 and sections 12.1-12.3
|
|
L4
|
Balanced binary search trees
|
CLRS, sections 13.1 and 13.2 for a different approach (red-black trees)
|
|
Hashing
|
|
|
|
L5
|
Hashing I: chaining, hash functions
|
|
|
L6
|
Hashing II:
table doubling, Karp-Rabin
|
CLRS,
chapter 17 and section 32.2
|
|
L7
|
Hashing
III: open addressing
|
CLRS,
section 11.4 (and 11.3.3 and 11.5 if interested)
|
|
Sorting
|
|
|
|
L8
|
Sorting I:
heaps
|
CLRS,
sections 2.1-2.3 and 6.1-6.2
|
|
L9
|
Sorting II:
heaps
|
CLRS,
sections 6.1-6.4
|
|
L10
|
Sorting
III: lower bounds, linear-time sorting
|
CLRS,
sections 8.1-8.4
|
|
L11
|
Sorting IV:
stable sorting, radix sort
|
|
|
Searching
|
|
|
|
L12
|
Searching
I: graph search, representations, and applications
|
CLRS,
sections 22.1-22.3 and B.4
|
|
L13
|
Searching
II: breadth-first search and depth-first search
|
CLRS,
sections 22.2-22.3
|
|
L14
|
Searching
III: topological sort and NP-completeness
|
CLRS,
sections 22.4 and 34.1-34.3 (at a high level)
|
|
Shortest
paths
|
|
|
|
L15
|
Shortest
paths I: intro
|
CLRS,
chapter 24 (intro)
|
|
L16
|
Shortest
paths II: Bellman-Ford
|
|
|
L17
|
Shortest
paths III: Dijkstra
|
CLRS,
sections 24.2-24.3
|
|
L18
|
Shortest
paths IV: Dijkstra speedups
|
Wagner,
Dorothea, and Thomas Willhalm. "Speed-Up Techniques for Shortest-Path
Computations." In Lecture Notes in Computer Science: Proceedings of
the 24th Annual Symposium on Theoretical Aspects of Computer Science.
Berlin / Heidelberg: Springer, 2007. ISBN: 9783540709176. Read up to section
3.2.
|
|
Dynamic
programming
|
|
|
|
L19
|
Dynamic programming
I: memoization, Fibonacci, Crazy Eights, guessing
|
CLRS,
chapter 15
|
|
L20
|
Dynamic
programming II: longest common subsequence, parent pointers
|
|
|
L21
|
Dynamic
programming III: text justification, parenthesization, knapsack,
pseudopolynomial time, Tetris training
|
|
|
L22
|
Dynamic
programming IV: piano fingering, structural DP (trees), vertex cover,
dominating set, and beyond
|
For fun,
see papers on piano fingering and polyphonic piano fingering via DP:
Parncutt,
Richard, et al. "An Ergonomic Model of Keyboard Fingering for Melodic
Fragments." Music Perception 14, no. 4 (1997): 341-382.
Al Kasimi,
Alia, Eric Nichols, and Christopher Raphael. "A Simple Algorithm for
Automatic Generation of Polyphonic Piano Fingerings." In Proceedings
of the 8th International Conference on Music Information Retrieval, 2007,
pp. 355-356.
For fun,
watch the Metamorphosis of the Cube video,
which illustrates a folding DP.
|
|
Numerics
|
|
|
|
L23
|
Numerics I
|
|
|
L24
|
Numerics II
|
|
|
Beyond
6.006
|
|
|
|
L25
|
Beyond
6.006: follow-on classes, geometric folding algorithms
|
|
