Introduction to Algorithms Notes PDF

Introduction to Algorithms Notes PDF

 

Rotation of a binary search tree, from the Recitation #4 slides. (Figure courtesy of Victor Costan.)

Course Highlights

This course features a full set of lecture notes and a set of detailed recitationslides.

Course Description

This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems. The course emphasizes the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems.

Technical Requirements

Special software is required to use some of the files in this course: .tex, .py, .rb, and .zip.

Click Below to Download the files :-

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 #	TOPICS	SUPPORTING FILES
Introduction and document distance
L1	Introduction and document distance (PDF)	Document distance(docdist{1,2,3,4}.py)
L2	More document distance, mergesort (PDF)	Document distance (docdist{5,6}.py)
Binary search trees
L3	Airplane scheduling, binary search trees (PDF - 1.4 MB)	Binary search trees (including code)
L4	Balanced binary search trees (PDF - 1.2 MB)	See binary search trees for AVL code
Hashing
L5	Hashing I: chaining, hash functions (PDF)	Document distance (docdist-dict.py)
L6	Hashing II: table doubling, Karp-Rabin (PDF)
L7	Hashing III: open addressing (PDF - 1.1 MB)
Sorting
L8	Sorting I: heaps (PDF - 1.0 MB)
L9	Sorting II: heaps (PDF)
L10	Sorting III: lower bounds, linear-time sorting (PDF)
L11	Sorting IV: stable sorting, radix sort (PDF - 1.0 MB)
Searching
L12	Searching I: graph search, representations, and applications (PDF - 1.6 MB)	Simple Python code for graphs (PY)
L13	Searching II: breadth-first search and depth-first search (PDF - 1.3 MB)
L14	Searching III: topological sort and NP-completeness (PDF)
Shortest paths
L15	Shortest paths I: intro (PDF - 1.0 MB)
L16	Shortest paths II: Bellman-Ford (PDF - 1.1 MB)
L17	Shortest paths III: Dijkstra (PDF)
L18	Shortest paths IV: Dijkstra speedups (PDF - 1.2 MB)
Dynamic programming
L19	Dynamic programming I: memoization, Fibonacci, Crazy Eights, guessing (PDF)
L20	Dynamic programming II: longest common subsequence, parent pointers (PDF)
L21	Dynamic programming III: text justification, parenthesization, knapsack, pseudopolynomial time, Tetris training (PDF)
L22	Dynamic programming IV: piano fingering, structural DP (trees), vertex cover, dominating set, and beyond (PDF)
Numerics
L23	Numerics 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.)
L24	Numerics II (PDF)