Lectures and Recitations

From 6.006 Introduction to Algorithms

Revision as of 12:48, 12 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.2, 2.3, 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]