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
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:
Post a Comment