Lectures and Recitations
From 6.006 Introduction to Algorithms
(Difference between revisions)
(→Sorting) |
(add lecture 12) |
||
| Line 55: | Line 55: | ||
=== Sorting === | === Sorting === | ||
==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture8.pdf Lecture 8], Sorting I: Heaps ==== | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture8.pdf Lecture 8], Sorting I: Heaps ==== | ||
| - | * Reading: CLRS, Sections 2.1 | + | * 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 ==== | ==== [[Recitation 8]], Overview of Sorting Methods; Heaps as Data Structures: Principles, Sorting, Priority Queues ==== | ||
* Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/HeapSort.pdf PDF]] | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/HeapSort.pdf PDF]] | ||
* Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation08.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation08.zip Zipped Keynote]] | * Victor's Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation08.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation08.zip Zipped Keynote]] | ||
==== [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 ==== | ||
* Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation09.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation09.zip Zipped Keynote]] | * Slides [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation09.pdf PDF]] | [[http://courses.csail.mit.edu/6.006/spring08/keynotes/recitation09.zip Zipped Keynote]] | ||
| Line 68: | Line 68: | ||
==== [[Recitation 10]], Counting,Radix and Bucket Sorting, Gas simulation ==== | ==== [[Recitation 10]], Counting,Radix and Bucket Sorting, Gas simulation ==== | ||
* Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/LinearTime_Sorting.pdf PDF]] | * Hueihan's Slides [[http://courses.csail.mit.edu/6.006/spring08/recitation_notes/LinearTime_Sorting.pdf PDF]] | ||
| + | |||
| + | === Searching === | ||
| + | ==== [http://courses.csail.mit.edu/6.006/spring08/notes/lecture12.pdf Lecture 12], Searching I: Graph Search, Representations, and Applications ==== | ||
| + | * Reading: CLRS, Sections 22.1-22.3 and B.4 | ||
Revision as of 03:25, 18 March 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
- Reading: CLRS, Sections 22.1-22.3 and B.4
