Reading task(Introduction to Algorithms. 2nd）
Introduction to Algorithms 2nd ed. Cambridge, MA: MIT Press, 2001. ISBN: 9780262032933.
| Introduction and document distance SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 |
|
|
| 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 |
|
