Lectures and Recitations
From 6.006 Introduction to Algorithms
(Difference between revisions)
m |
|||
| Line 1: | Line 1: | ||
| - | + | === Introduction and Document Distance === | |
| - | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture1.pdf 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 [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation01.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation01.zip Zipped Keynote]] | ||
| - | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture2.pdf 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 [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation02.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation02.zip Zipped Keynote]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation02_data.zip Zipped Data (Numbers)]] | |
| - | + | * [[Python Cost Model]] | |
| - | + | === Binary Search Trees === | |
| - | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture3.pdf 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 [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation03.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation03.zip Zipped Keynote]] | |
| - | + | * Code for Binary Search Trees augmented with subtree size [[http://courses.csail.mit.edu/6.006/spring08/keynotes/bstsize_r.py Python]] | |
| - | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture4.pdf 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) | |
| - | + | * [http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html AVL tree animation applet] | |
| - | + | ==== [[Recitation 4]], AVL Trees (Balanced Binary Search Trees) ==== | |
| - | + | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/AVLClass.pdf PDF ]] | |
| - | + | * Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation04.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation04.zip Zipped Keynote]] | |
| - | + | * Code for AVL Trees: [[http://courses.csail.mit.edu/6.006/spring08/keynotes/avl_r.py Python]] (uses the BST code from Recitation 3) | |
| - | + | === Hashing === | |
| - | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture5.pdf Lecture 5], Hashing I: Chaining, Hash Functions ==== | |
| + | * [[Document Distance]] (docdist-dict.py) | ||
| - | + | ==== [[Recitation 5]] Hashing in Python, Mutability ==== | |
| - | + | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/PythonHashing.pdf PDF ]] | |
| - | + | * Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation05.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation05.zip Zipped Keynote]] | |
| - | + | * The dangers of mutable dictionary keys: [[http://courses.csail.mit.edu/6.006/spring08/keynotes/mutable_dictkey.py Python Demo]] | |
| - | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture6.pdf 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 [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation06.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation06.zip Zipped Keynote]] | |
| - | + | * Super-awesome Rolling Hash code: [[http://courses.csail.mit.edu/6.006/spring08/keynotes/rolling_hash.py Python]] | |
| - | + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture7.pdf Lecture 7], Hashing III: Open Addressing ==== | |
| - | + | * Reading: CLRS, Section 11.4 (and 11.3.3 and 11.5 if interested) | |
Revision as of 10:51, 28 February 2008
Contents |
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)
