Courses:

Introduction to Algorithms >> Content Detail



Lecture Notes



Lecture Notes

Special software is required to use some of the files in this section: .py and .zip.

The lecture notes in this section were transcribed from the professors' handwritten notes by graduate student Pavitra Krishnaswamy. The handwritten notes can be found on the Lectures and Recitations page of the original 6.006 Web site.


LEC #TOPICSSUPPORTING FILES
Introduction and document distance
L1Introduction and document distance (PDF)Document distance (docdist{1,2,3,4}.py)
L2More document distance, mergesort (PDF)Document distance (docdist{5,6}.py)
Binary search trees
L3Airplane scheduling, binary search trees (PDF - 1.4 MB)Binary search trees (including code)
L4Balanced binary search trees (PDF - 1.4 MB)See binary search trees for AVL code
Hashing
L5Hashing I: chaining, hash functions (PDF)Document distance (docdist-dict.py)
L6Hashing II: table doubling, Karp-Rabin (PDF)
L7Hashing III: open addressing (PDF - 1.1 MB)
Sorting
L8Sorting I: heaps (PDF - 1.0 MB)
L9Sorting II: heaps (PDF)
L10Sorting III: lower bounds, linear-time sorting (PDF)
L11Sorting IV: stable sorting, radix sort (PDF - 1.0 MB)
Searching
L12Searching I: graph search, representations, and applications (PDF - 1.6 MB)Simple Python code for graphs (PY)
L13Searching II: breadth-first search and depth-first search (PDF - 1.3 MB)
L14Searching III: topological sort and NP-completeness (PDF)
Shortest paths
L15Shortest paths I: intro (PDF - 1.0 MB)
L16Shortest paths II: Bellman-Ford (PDF - 1.1 MB)
L17Shortest paths III: Dijkstra (PDF)
L18Shortest paths IV: Dijkstra speedups (PDF - 1.2 MB)
Dynamic programming
L19Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing (PDF)
L20Dynamic programming II: longest common subsequence, parent pointers (PDF)
L21Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris training (PDF)
L22Dynamic programming IV: piano fingering, structural DP (trees), vertex cover, dominating set, and beyond (PDF)
Numerics
L23Numerics I (PDF)

Demos: square root of 2, chord length

Source code (ZIP) (This zip file includes: 14 .js files, 2 .html files, 1 .css file, and 1 .project file.)

L24Numerics II (PDF)
Beyond 6.006
L25Beyond 6.006: follow-on classes, geometric folding algorithms (PDF)If you are interested in folding algorithms, you can look at the previous offering of 6.885 and the associated textbook.

 








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