Introduction to Algorithms

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.

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)
Beyond 6.006
L25
Beyond 6.006: follow-on classes, geometric folding algorithms (PDF)
If you are interested in folding algorithms, you can look at theprevious offering of 6.885 and theassociated textbook.

Exams and solutions

This section contains practice questions and solutions for the two quizzes and the final exam.

Quiz 1

Practice Questions (PDF)
Practice Solutions (PDF)

Quiz 2

Practice Questions (PDF)
Practice Solutions (PDF)

Final Exam

Practice Questions (PDF)
Practice Solutions (PDF)

No comments: