Lectures and Recitations
From 6.006: Introduction to Algorithms
(Difference between revisions)
| (41 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L01/L01_Lecture_Notes.pdf Lecture 1]: Introduction, Document Distance | ||
| + | ** [[Document Distance]] | ||
| + | ** Readings: CLRS, chapters 1, 2, 3. | ||
* [[Recitation 1]]: Document Distance; Python Lists | * [[Recitation 1]]: Document Distance; Python Lists | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L02/L02_Lecture_Notes.pdf 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 | * [[Recitation 2]]: Document Distance; Flatten | ||
| − | * [[Recitation 3]]: Maximum Contiguous | + | |
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L03/L03_Lecture_Notes.pdf Lecture 3]: Document Distance (3) | ||
| + | ** [[Document Distance Program Version 6]], [http://courses.csail.mit.edu/6.006/fall07/source/mergesort.py mergesort.py] | ||
| + | ** [http://courses.csail.mit.edu/6.006/fall07/logs/L03-classlog.txt Python log from lecture] | ||
| + | * [[Recitation 3]]: Maximum Contiguous Subarray | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L04/L04_Lecture_Notes.pdf Lecture 4]: Binary Search Trees | ||
| + | ** Readings: CLRS, chapter 10, and chapter 12, sections 1–3. | ||
* [[Recitation 4]]: BST Augmentation; Python OO | * [[Recitation 4]]: BST Augmentation; Python OO | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L05/L05_Lecture_Notes.pdf Lecture 5]: Balanced Binary Search Trees | ||
| + | ** See [http://courses.csail.mit.edu/6.006/fall07/resources.shtml#bst 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 | * [[Recitation 5]]: Rotations; Balanced BSTs | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L06/L06_Lecture_Notes.pdf Lecture 6]: Hashing (1) | ||
| + | ** Readings [http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/11608C3D-CF70-4D0A-8153-E836FDB9515A/0/lec7.pdf Lecture slides from OCW], CLRS, chapter 11, sections 1 and 2. | ||
* [[Recitation 6]]: Hashing; hash() | * [[Recitation 6]]: Hashing; hash() | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L07/L07_Lecture_Notes.pdf Lecture 7]: Hashing (2) | ||
| + | ** Readings: CLRS, 11.3 and 32.2. | ||
* [[Recitation 7]]: String Matching; Rabin-Karp | * [[Recitation 7]]: String Matching; Rabin-Karp | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L08/L08_Lecture_Notes.pdf Lecture 8]: Hashing (3) | ||
| + | ** Readings: CLRS, chapter 11, section 4. | ||
* [[Recitation 8]]: Hash Tables | * [[Recitation 8]]: Hash Tables | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L09/L09_Lecture_Notes.pdf Lecture 9]: Dynamic Programming (1) | ||
| + | ** Readings: CLRS, 15.1–15.3. | ||
* [[Recitation 9]]: Image Resizing; Matrix Chain Multiplication | * [[Recitation 9]]: Image Resizing; Matrix Chain Multiplication | ||
* [[Recitation 10]]: Stamps; Longest Increasing Subsequence; Knapsack | * [[Recitation 10]]: Stamps; Longest Increasing Subsequence; Knapsack | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L10/L10_Lecture_Notes.pdf Lecture 10]: Dynamic Programming (2) | ||
| + | ** [http://courses.csail.mit.edu/6.006/fall07/handouts/compress.pdf Image Compression Handout] | ||
| + | * [[Recitation 11]]: Shortest vs. Longest Path; 1 Dimensional Image compression | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L11/L11_Lecture_Notes.pdf Lecture 11]: Dynamic Programming (3) | ||
| + | ** Readings: CLRS, 15.3–15.4. | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L12/L12_Lecture_Notes.pdf Lecture 12]: Dynamic Programming (4) | ||
| + | * [[Recitation 12]]: Quiz review; Tris | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L13/L13_Lecture_Notes.pdf Lecture 13]: Sorting (1) Heaps | ||
| + | ** Readings: CLRS, 6.1, 6.2. | ||
| + | * [[Recitation 13]]: Max-heapify, Building a heap | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L14/L14_Lecture_Notes.pdf Lecture 14]: Sorting (2) Heaps | ||
| + | ** Readings: CLRS, 6.3, 6.4. | ||
| + | * [[Recitation 14]]: Priority Queues (CLRS 6.5) | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L15/L15_Lecture_Notes.pdf Lecture 15]: Sorting (3) Counting Sort | ||
| + | ** Readings: CLRS, 8.1, 8.2 | ||
| + | * [[Recitation 15]]: Gas Simulation | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L16/L16_Lecture_Notes.pdf Lecture 16]: Sorting (4) Radix Sort | ||
| + | ** [http://cg.scs.carleton.ca/~morin/misc/sortalg/ Sorting algorithms race] | ||
| + | ** Readings: CLRS, 8.3, 8.4 | ||
| + | * [[Recitation 16]]: Quick sort; Bucket Sort | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L17/L17_Lecture_Notes.pdf Lecture 17]: Search (1) | ||
| + | ** Readings: CLRS, 22.1, 22.2, Appendix B.4 | ||
| + | * [[Recitation 17]]: Graph representations; Rubik's cube representations. | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L18/L18_Lecture_Notes.pdf Lecture 18]: Search (2) BFS | ||
| + | ** Readings: CLRS, 22.2, 10.1 (Queues) | ||
| + | * [[Recitation 18]]: Breadth First Trees; 2-way BFS. | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L19/L19_Lecture_Notes.pdf Lecture 19]: Search (3) DFS | ||
| + | ** Readings: CLRS, 22.3, 22.4 | ||
| + | * [[Recitation 19]]: BFS and DFS; Articulation Points | ||
| + | |||
| + | * [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 | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L21/L21_Lecture_Notes.pdf Lecture 21]: Shortest Paths (2) Bellman-Ford | ||
| + | ** Readings: CLRS, 24.1 | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L22/L22_Lecture_Notes.pdf Lecture 22]: Shortest Paths (3) Dijkstra | ||
| + | ** Readings: CLRS, 24.2, 24.3 | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L23/L23_Lecture_Notes.pdf Lecture 23]: Shortest Paths (4) Dijkstra & Potentials | ||
| + | ** Readings: [[s07fall:handouts/protected/L23/L23-Dijkstra-Speedups.PDF|Dijsktra speedups paper]], [[Dijkstra speedups corrections]] | ||
| + | * [[Recitation 21]] Dijkstra homework problem; detailed review of priority queue/heaps. | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L24/L24_Lecture_Notes.pdf Lecture 24]: Numerics (1) | ||
| + | * [[Recitation 22]] Strassen Matrix Multiplication; Master Method | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L25/L25_Lecture_Notes.pdf Lecture 25]: Numerics (2) | ||
| + | ** [http://courses.csail.mit.edu/6.006/fall07/source/sqrt.py sqrt.py] | ||
| + | * [[Recitation 23]] Newton's Method with fractions; Radix Conversion | ||
| + | |||
| + | * [https://courses.csail.mit.edu/6.006/fall07/handouts/protected/L26/L26_Lecture_Notes.pdf Lecture 26]: Future classes | ||
Latest revision as of 21:48, 30 January 2008
- 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: Max-heapify, Building a heap
- 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
- Lecture 21: Shortest Paths (2) Bellman-Ford
- Readings: CLRS, 24.1
- Lecture 22: Shortest Paths (3) Dijkstra
- Readings: CLRS, 24.2, 24.3
- Lecture 23: Shortest Paths (4) Dijkstra & Potentials
- Recitation 21 Dijkstra homework problem; detailed review of priority queue/heaps.
- Lecture 24: Numerics (1)
- Recitation 22 Strassen Matrix Multiplication; Master Method
- Lecture 25: Numerics (2)
- Recitation 23 Newton's Method with fractions; Radix Conversion
- Lecture 26: Future classes
