Lectures and Recitations
From 6.006 Introduction to Algorithms
(Difference between revisions)
(→[http://courses.csail.mit.edu/6.006/spring08/notes/lecture20.pdf Lecture 20], Dynamic Programming II: Longest Common Subsequence, Parent Pointers) |
m (→Recitation 23, Review for the Final Exam) |
||
| (44 intermediate revisions not shown) | |||
| Line 61: | Line 61: | ||
==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture9.pdf Lecture 9], Sorting II: Heaps ==== | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture9.pdf Lecture 9], Sorting II: Heaps ==== | ||
* Reading: CLRS, Sections 6.1-6.4 | * Reading: CLRS, Sections 6.1-6.4 | ||
| - | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture10.pdf Lecture 10], Sorting III: Lower Bounds, Linear Time Sorting ==== | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture10.pdf Lecture 10], Sorting III: Lower Bounds, Linear-Time Sorting ==== |
* Reading: CLRS, Sections 8.1-8.4 | * Reading: CLRS, Sections 8.1-8.4 | ||
==== [[Recitation 9]], Quiz Review: Interesting Problems ==== | ==== [[Recitation 9]], Quiz Review: Interesting Problems ==== | ||
| Line 87: | Line 87: | ||
==== [[Recitation 13]], Assistance for PS ==== | ==== [[Recitation 13]], Assistance for PS ==== | ||
* Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation12.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation12.zip Zipped Keynote]] | * Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation12.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation12.zip Zipped Keynote]] | ||
| - | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture16.pdf Lecture 16], Shortest Paths II: Bellman Ford ==== | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture16.pdf Lecture 16], Shortest Paths II: Bellman-Ford ==== |
==== [[Recitation 14]], Generic Shortest-Path Algorithm: Concepts, Properties; Bellman-Ford: Examples, Negative-Cost Cycles ==== | ==== [[Recitation 14]], Generic Shortest-Path Algorithm: Concepts, Properties; Bellman-Ford: Examples, Negative-Cost Cycles ==== | ||
No slides, you had to be there to get the material :) | No slides, you had to be there to get the material :) | ||
| Line 95: | Line 95: | ||
==== [[Recitation 15]], Hands-on Dijkstra: Pseudocode, Preconditions, Examples, Why It Works; Priority Queues: Review, Extended Python Implementation ==== | ==== [[Recitation 15]], Hands-on Dijkstra: Pseudocode, Preconditions, Examples, Why It Works; Priority Queues: Review, Extended Python Implementation ==== | ||
* Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation13.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation13.zip Zipped Keynote]] | * Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation13.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation13.zip Zipped Keynote]] | ||
| - | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture18.pdf Lecture 18], Shortest Paths IV: Dijkstra | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture18.pdf Lecture 18], Shortest Paths IV: Dijkstra Speedups ==== |
* Reading: [https://courses.csail.mit.edu/6.006/spring08/handouts/protected/wagner.pdf Wagner Paper] up to section 3.2 | * Reading: [https://courses.csail.mit.edu/6.006/spring08/handouts/protected/wagner.pdf Wagner Paper] up to section 3.2 | ||
==== [[Recitation 16]], Array implementation of Dijkstra ==== | ==== [[Recitation 16]], Array implementation of Dijkstra ==== | ||
| Line 103: | Line 103: | ||
==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture19.pdf Lecture 19], Dynamic Programming I: Memoization, Fibonacci, Crazy Eights, Guessing ==== | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture19.pdf Lecture 19], Dynamic Programming I: Memoization, Fibonacci, Crazy Eights, Guessing ==== | ||
* Reading: CLRS, Chapter 15 | * Reading: CLRS, Chapter 15 | ||
| + | ==== [[Recitation 17]], Hands-on Dynamic Programming: Big Ideas, Memoization in Fibonacci, Crazy Cards, Dijkstra and Bellman Ford Algorithm as dynamic Programming ==== | ||
| + | * Victor's Notes [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation17.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation17.docx DOCX (MS Word 2007+)]] | ||
==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture20.pdf Lecture 20], Dynamic Programming II: Longest Common Subsequence, Parent Pointers ==== | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture20.pdf Lecture 20], Dynamic Programming II: Longest Common Subsequence, Parent Pointers ==== | ||
| - | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/DynamicProgramming. | + | ==== [[Recitation 18]], More Dynamic Programming: Beating Super Mario Bros, Getting Points Back on Tests (LCS), Crazy Eights ==== |
| + | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/DynamicProgramming.pdf PDF]] | ||
| + | * Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation18.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation18.zip Zipped Keynote]] | ||
| + | * Beating Super Mario Brothers: [[http://www.youtube.com/watch?v=9yl_XPkcTl4 YouTube Video]] | ||
| + | * The concept of Pure Pwnage: [[http://www.youtube.com/watch?v=DL2HAwZ6fzM YouTube Video]] | ||
| + | |||
| + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture21.pdf Lecture 21], Dynamic Programming III: Text Justification, Parenthesization, Knapsack, Pseudopolynomial Time, Tetris Training ==== | ||
| + | |||
| + | ==== [[Recitation 19]], Even More Dynamic Programming: Maxiumum-sum Sub-array, Pwning at Tetris ==== | ||
| + | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/MoreDP.pdf PDF]] | | ||
| + | * Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation19.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation19.zip Zipped Keynote]] | ||
| + | * Pure Pwnage applied to Tetris: [[http://www.youtube.com/watch?v=40Eut5pPpmQ YouTube Video]] | ||
| + | |||
| + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture22.pdf Lecture 22], Dynamic Programming IV: Piano Fingering, Structural DP (Trees), Vertex Cover, Dominating Set, Beyond ==== | ||
| + | * For fun, see papers on [http://www-gewi.uni-graz.at/staff/parncutt/publications/PaSlClRaDe97_FingeringModel.pdf piano fingering] and [http://ismir2007.ismir.net/proceedings/ISMIR2007_p355_kasimi.pdf polyphonic piano fingering] via DP. | ||
| + | * For fun, watch the [http://erikdemaine.org/metamorphosis/ Metamorphosis of the Cube] video, which illustrates a folding DP. | ||
| + | |||
| + | ==== [[Recitation 20]], Knapsack and Its Variants, Structural Dynamic Programming: Covering a Tree with Templates, Dominating Set ==== | ||
| + | * Covering a Tree with Templates | ||
| + | ** Problem statement and original solution [[http://courses.csail.mit.edu/6.006/spring08/keynotes/tree_templates_p3.pdf PDF]] | ||
| + | ** Victor's solution during the quiz [[http://courses.csail.mit.edu/6.006/spring08/keynotes/tree_templates_vc.pdf PDF]] (read and stop complaining about long psets :P) | ||
| + | * Dominating Set: the problem and solution are described in the [http://courses.csail.mit.edu/6.006/spring08/notes/lecture22.pdf Lecture 22 Notes] | ||
| + | |||
| + | === Numerics === | ||
| + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture23.pdf Lecture 23], Numerics I ==== | ||
| + | * Demos (tested on IE 7, Firefox 2/3 or Safari 3; the latter renders the prettiest results) | ||
| + | ** Square Root of 2 [[http://courses.csail.mit.edu/6.006/spring08/keynotes/numerics_demo/sqrt2.html XHTML/JS]] | ||
| + | ** Chord Length [[http://courses.csail.mit.edu/6.006/spring08/keynotes/numerics_demo/chord.html XHTML/JS]] | ||
| + | ** Source code [[http://courses.csail.mit.edu/6.006/spring08/keynotes/numerics_demo.zip Zip]] | ||
| + | |||
| + | ==== [[Recitation 21]], Dynamic Programming Practice: Live Python Coding, Dominating Sets, Structural Dynamic Programming: Covering a Tree with Templates ==== | ||
| + | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/MoreMoreDP.pdf PDF]] | | ||
| + | * The problems for the Live Python Coding (problem statement, tests, and solutions are included): | ||
| + | ** Matrix Chain Multiplication [[http://courses.csail.mit.edu/6.006/spring08/keynotes/r21_parens.zip Zip]] | ||
| + | ** Longest Zig-Zag Subsequence [[http://courses.csail.mit.edu/6.006/spring08/keynotes/r21_sequence.zip Zip]] | ||
| + | * Dominating Set: the problem and solution are described in the [http://courses.csail.mit.edu/6.006/spring08/notes/lecture22.pdf Lecture 22 Notes] | ||
| + | |||
| + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture24.pdf Lecture 24], Numerics II ==== | ||
| + | ==== [[Recitation 22(1)(2)]], Divide and Conquer vs Dynamic Programming on Problems: Matrix Multiplication, Tower, Max-sum Subarray, Closet Pair ==== | ||
| + | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/Divide_conquer_problems.pdf PDF]] | | ||
| + | * MaxSumSubarray[[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/Bentley-ProgrammingPearl.pdf PDF]] | ||
| + | ==== [[Recitation 22(3)(4)]], Numerics Review, Strassen's Algorithm for Matrix Multiplication ==== | ||
| + | * The material we reviewed is covered in the lecture notes for [[http://courses.csail.mit.edu/6.006/spring08/notes/lecture23.pdf Lecture 23: Numerics I]] and [[http://courses.csail.mit.edu/6.006/spring08/notes/lecture23.pdf Lecture 24: Numerics II]] | ||
| + | * Strassen's algorithm for fast matrix multiplication is covered in CLRS, Chapter 28, pages 735-742 | ||
| + | |||
| + | === Beyond 6.006 === | ||
| + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture25.pdf Lecture 25], Beyond 6.006: Follow-on Classes, Geometric Folding Algorithms ==== | ||
| + | * If you are interested in folding algorithms, you can look at the [http://courses.csail.mit.edu/6.885/fall07/ previous offering of 6.885] and the [http://www.gfalop.org/ associated textbook]. | ||
| + | |||
| + | ==== [[Recitation 23]], Review for the Final Exam ==== | ||
| + | * Victor's Slides (BETA = incomplete) [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation23.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation23.zip Zipped Keynote]] | ||
Latest revision as of 18:51, 19 May 2008
Introduction and Document Distance
Lecture 1, Introduction and Document Distance
- Document Distance (docdist{1,2,3,4}.py)
- Readings: CLRS, Chapters 1, 2, 3.
Recitation 1, Document Distance in Python (docdist{1,2,3,4}.py)
- Victor's Slides [PDF] | [Zipped Keynote]
Lecture 2, More Document Distance, Mergesort
- Document Distance (docdist{5,6}.py)
- Readings: CLRS, Sections 11.1 and 11.2.
Recitation 2, Python Cost Model, Review for Asymptotic Notation & Mergesort
- Victor's Slides [PDF] | [Zipped Keynote] | [Zipped Data (Numbers)]
- Python Cost Model
Binary Search Trees
Lecture 3, Airplane scheduling; Binary Search Trees
- Binary Search Trees (including code)
- Readings: CLRS, Chapter 10 and Sections 12.1-12.3
Recitation 3, Binary Search Trees
- Victor's Slides [PDF] | [Zipped Keynote]
- Code for Binary Search Trees augmented with subtree size [Python]
Lecture 4, Balanced Binary Search Trees
- See Binary Search Trees for AVL code
- Readings: CLRS, Sections 13.1 and 13.2 for a different approach (red-black trees)
- AVL tree animation applet
Recitation 4, AVL Trees (Balanced Binary Search Trees)
- Hueihan's Slides [PDF ]
- Victor's Slides [PDF] | [Zipped Keynote]
- Code for AVL Trees: [Python] (uses the BST code from Recitation 3)
Hashing
Lecture 5, Hashing I: Chaining, Hash Functions
- Document Distance (docdist-dict.py)
Recitation 5, Hashing in Python, Mutability
- Hueihan's Slides [PDF ]
- Victor's Slides [PDF] | [Zipped Keynote]
- The dangers of mutable dictionary keys: [Python Demo]
Lecture 6, Hashing II: Table Doubling, Karp-Rabin
- Reading: CLRS, Chapter 17 and Section 32.2
Recitation 6, Karp-Rabin review, Rolling Hashes principles and code
- Victor's Slides [PDF] | [Zipped Keynote]
- Super-awesome Rolling Hash code: [Python]
Lecture 7, Hashing III: Open Addressing
- Reading: CLRS, Section 11.4 (and 11.3.3 and 11.5 if interested)
Recitation 7, Open Addressing: theory review, Python code; More Rolling Hashes (for Rabin Karp)
- Victor's Slides [PDF] | [Zipped Keynote]
- Open Addressing code: [Python]
Sorting
Lecture 8, Sorting I: Heaps
- Reading: CLRS, Sections 2.1-2.3 and 6.1-6.2
Recitation 8, Overview of Sorting Methods; Heaps as Data Structures: Principles, Sorting, Priority Queues
- Hueihan's Slides [PDF]
- Victor's Slides [PDF] | [Zipped Keynote]
Lecture 9, Sorting II: Heaps
- Reading: CLRS, Sections 6.1-6.4
Lecture 10, Sorting III: Lower Bounds, Linear-Time Sorting
- Reading: CLRS, Sections 8.1-8.4
Recitation 9, Quiz Review: Interesting Problems
- Slides [PDF] | [Zipped Keynote]
Lecture 11, Sorting IV: Stable Sorting, Radix Sort
Recitation 10, Counting,Radix and Bucket Sorting, Gas simulation
- Hueihan's Slides [PDF]
Searching
Lecture 12, Searching I: Graph Search, Representations, and Applications
- Simple Python code for graphs
- Reading: CLRS, Sections 22.1-22.3 and B.4
Lecture 13, Searching II: Breadth-First Search and Depth-First Search
- Reading: CLRS, Sections 22.2-22.3
Lecture 14, Searching III: Topological Sort and NP-completeness
- Reading: CLRS, Sections 22.4 and 34.1-34.3 (at a high level)
Recitation 12, BFS and DFS
- Python code for breadth-first-search
- Python code for depth-first-search
- Victor's Slides [PDF] | [Zipped Keynote]
Shortest Paths
Lecture 15, Shortest Paths I: Intro
- Reading: CLRS, Chapter 24 (Intro)
Recitation 13, Assistance for PS
- Victor's Slides [PDF] | [Zipped Keynote]
Lecture 16, Shortest Paths II: Bellman-Ford
Recitation 14, Generic Shortest-Path Algorithm: Concepts, Properties; Bellman-Ford: Examples, Negative-Cost Cycles
No slides, you had to be there to get the material :)
Lecture 17, Shortest Paths III: Dijkstra
- Reading: CLRS, 24.2, 24.3
Recitation 15, Hands-on Dijkstra: Pseudocode, Preconditions, Examples, Why It Works; Priority Queues: Review, Extended Python Implementation
- Victor's Slides [PDF] | [Zipped Keynote]
Lecture 18, Shortest Paths IV: Dijkstra Speedups
- Reading: Wagner Paper up to section 3.2
Recitation 16, Array implementation of Dijkstra
Dynamic Programming
Lecture 19, Dynamic Programming I: Memoization, Fibonacci, Crazy Eights, Guessing
- Reading: CLRS, Chapter 15
Recitation 17, Hands-on Dynamic Programming: Big Ideas, Memoization in Fibonacci, Crazy Cards, Dijkstra and Bellman Ford Algorithm as dynamic Programming
- Victor's Notes [PDF] | [DOCX (MS Word 2007+)]
Lecture 20, Dynamic Programming II: Longest Common Subsequence, Parent Pointers
Recitation 18, More Dynamic Programming: Beating Super Mario Bros, Getting Points Back on Tests (LCS), Crazy Eights
- Hueihan's Slides [PDF]
- Victor's Slides [PDF] | [Zipped Keynote]
- Beating Super Mario Brothers: [YouTube Video]
- The concept of Pure Pwnage: [YouTube Video]
Lecture 21, Dynamic Programming III: Text Justification, Parenthesization, Knapsack, Pseudopolynomial Time, Tetris Training
Recitation 19, Even More Dynamic Programming: Maxiumum-sum Sub-array, Pwning at Tetris
- Hueihan's Slides [PDF] |
- Victor's Slides [PDF] | [Zipped Keynote]
- Pure Pwnage applied to Tetris: [YouTube Video]
Lecture 22, Dynamic Programming IV: Piano Fingering, Structural DP (Trees), Vertex Cover, Dominating Set, Beyond
- For fun, see papers on piano fingering and polyphonic piano fingering via DP.
- For fun, watch the Metamorphosis of the Cube video, which illustrates a folding DP.
Recitation 20, Knapsack and Its Variants, Structural Dynamic Programming: Covering a Tree with Templates, Dominating Set
- Covering a Tree with Templates
- Dominating Set: the problem and solution are described in the Lecture 22 Notes
Numerics
Lecture 23, Numerics I
- Demos (tested on IE 7, Firefox 2/3 or Safari 3; the latter renders the prettiest results)
Recitation 21, Dynamic Programming Practice: Live Python Coding, Dominating Sets, Structural Dynamic Programming: Covering a Tree with Templates
- Hueihan's Slides [PDF] |
- The problems for the Live Python Coding (problem statement, tests, and solutions are included):
- Dominating Set: the problem and solution are described in the Lecture 22 Notes
Lecture 24, Numerics II
Recitation 22(1)(2), Divide and Conquer vs Dynamic Programming on Problems: Matrix Multiplication, Tower, Max-sum Subarray, Closet Pair
Recitation 22(3)(4), Numerics Review, Strassen's Algorithm for Matrix Multiplication
- The material we reviewed is covered in the lecture notes for [Lecture 23: Numerics I] and [Lecture 24: Numerics II]
- Strassen's algorithm for fast matrix multiplication is covered in CLRS, Chapter 28, pages 735-742
Beyond 6.006
Lecture 25, Beyond 6.006: Follow-on Classes, Geometric Folding Algorithms
- If you are interested in folding algorithms, you can look at the previous offering of 6.885 and the associated textbook.
Recitation 23, Review for the Final Exam
- Victor's Slides (BETA = incomplete) [PDF] | [Zipped Keynote]
