Courses:

Introduction to Algorithms >> Content Detail



Study Materials



Readings


Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

In the table below, readings listed as CLRS are taken from the course textbook:

Amazon logo Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press, 2001. ISBN: 9780262032933.


LEC #TOPICSREADINGS
Introduction and document distance
L1Introduction and document distanceCLRS, chapters 1-3
L2More document distance, mergesortCLRS, sections 11.1-11.2
Binary search trees
L3Airplane scheduling, binary search treesCLRS, chapter 10 and sections 12.1-12.3
L4Balanced binary search treesCLRS, sections 13.1 and 13.2 for a different approach (red-black trees)
Hashing
L5Hashing I: chaining, hash functions
L6Hashing II: table doubling, Karp-RabinCLRS, chapter 17 and section 32.2
L7Hashing III: open addressingCLRS, section 11.4 (and 11.3.3 and 11.5 if interested)
Sorting
L8Sorting I: heapsCLRS, sections 2.1-2.3 and 6.1-6.2
L9Sorting II: heapsCLRS, sections 6.1-6.4
L10Sorting III: lower bounds, linear-time sortingCLRS, sections 8.1-8.4
L11Sorting IV: stable sorting, radix sort
Searching
L12Searching I: graph search, representations, and applicationsCLRS, sections 22.1-22.3 and B.4
L13Searching II: breadth-first search and depth-first searchCLRS, sections 22.2-22.3
L14Searching III: topological sort and NP-completenessCLRS, sections 22.4 and 34.1-34.3 (at a high level)
Shortest paths
L15Shortest paths I: introCLRS, chapter 24 (intro)
L16Shortest paths II: Bellman-Ford
L17Shortest paths III: DijkstraCLRS, sections 24.2-24.3
L18Shortest paths IV: Dijkstra speedups

Amazon logo 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
L19Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessingCLRS, chapter 15
L20Dynamic programming II: longest common subsequence, parent pointers
L21Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris training
L22Dynamic 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
L23Numerics I
L24Numerics II
Beyond 6.006
L25Beyond 6.006: follow-on classes, geometric folding algorithms

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.