Lectures and Recitations
From 6.006: Introduction to Algorithms
(Difference between revisions)
| Line 81: | Line 81: | ||
* [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L20/L20_Lecture_Notes.pdf Lecture 20]: Shortest Paths (1) | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L20/L20_Lecture_Notes.pdf Lecture 20]: Shortest Paths (1) | ||
| + | ** Readings: CLRS, 24 intro | ||
| + | * [[Recitation 20]] Shortest Path Properties | ||
Revision as of 18:52, 16 November 2007
- Lecture 1: Introduction, Document Distance
- Document Distance
- Readings: CLRS, chapters 1, 2, 3.
- Recitation 1: Document Distance; Python Lists
- Lecture 2: Document Distance (2)
- Document Distance Program Version 3, Document Distance Program Version 4, Document Distance Program Version 5
- Readings: CLRS, chapter 11, sections 1 and 2.
- Resources: Python Cost Model
- Recitation 2: Document Distance; Flatten
- Lecture 3: Document Distance (3)
- Recitation 3: Maximum Contiguous Subarray
- Lecture 4: Binary Search Trees
- Readings: CLRS, chapter 10, and chapter 12, sections 1–3.
- Recitation 4: BST Augmentation; Python OO
- Lecture 5: Balanced Binary Search Trees
- See references page for papers with proofs relating to balanced BSTs.
- Readings: CLRS, chapter 13, sections 1 and 2 (warning: red-black trees -- read for culture).
- Recitation 5: Rotations; Balanced BSTs
- Lecture 6: Hashing (1)
- Readings Lecture slides from OCW, CLRS, chapter 11, sections 1 and 2.
- Recitation 6: Hashing; hash()
- Lecture 7: Hashing (2)
- Readings: CLRS, 11.3 and 32.2.
- Recitation 7: String Matching; Rabin-Karp
- Lecture 8: Hashing (3)
- Readings: CLRS, chapter 11, section 4.
- Recitation 8: Hash Tables
- Lecture 9: Dynamic Programming (1)
- Readings: CLRS, 15.1–15.3.
- Recitation 9: Image Resizing; Matrix Chain Multiplication
- Recitation 10: Stamps; Longest Increasing Subsequence; Knapsack
- Lecture 10: Dynamic Programming (2)
- Recitation 11: Shortest vs. Longest Path; 1 Dimensional Image compression
- Lecture 11: Dynamic Programming (3)
- Readings: CLRS, 15.3–15.4.
- Lecture 12: Dynamic Programming (4)
- Recitation 12: Quiz review; Tris
- Lecture 13: Sorting (1) Heaps
- Readings: CLRS, 6.1, 6.2.
- Recitation 13:
- Lecture 14: Sorting (2) Heaps
- Readings: CLRS, 6.3, 6.4.
- Recitation 14: Priority Queues (CLRS 6.5)
- Lecture 15: Sorting (3) Counting Sort
- Readings: CLRS, 8.1, 8.2
- Recitation 15: Gas Simulation
- Lecture 16: Sorting (4) Radix Sort
- Sorting algorithms race
- Readings: CLRS, 8.3, 8.4
- Recitation 16: Quick sort; Bucket Sort
- Lecture 17: Search (1)
- Readings: CLRS, 22.1, 22.2, Appendix B.4
- Recitation 17: Graph representations; Rubik's cube representations.
- Lecture 18: Search (2) BFS
- Readings: CLRS, 22.2, 10.1 (Queues)
- Recitation 18: Breadth First Trees; 2-way BFS.
- Lecture 19: Search (3) DFS
- Readings: CLRS, 22.3, 22.4
- Recitation 19: BFS and DFS; Articulation Points
- Lecture 20: Shortest Paths (1)
- Readings: CLRS, 24 intro
- Recitation 20 Shortest Path Properties
