Lectures and Recitations

From 6.006 Introduction to Algorithms

Contents 1 Introduction and Document Distance 1.1 Lecture 1, Introduction and Document Distance 1.2 Recitation 1, Document Distance in Python (docdist{1,2,3,4}.py) 1.3 Lecture 2, More Document Distance, Mergesort 1.4 Recitation 2, Python Cost Model, Review for Asymptotic Notation & Mergesort 2 Binary Search Trees 2.1 Lecture 3, Airplane scheduling; Binary Search Trees 2.2 Recitation 3, Binary Search Trees 2.3 Lecture 4, Balanced Binary Search Trees 2.4 Recitation 4, AVL Trees (Balanced Binary Search Trees) 3 Hashing 3.1 Lecture 5, Hashing I: Chaining, Hash Functions 3.2 Recitation 5, Hashing in Python, Mutability 3.3 Lecture 6, Hashing II: Table Doubling, Karp-Rabin 3.4 Recitation 6, Karp-Rabin review, Rolling Hashes principles and code 3.5 Lecture 7, Hashing III: Open Addressing 3.6 Recitation 7, Open Addressing: theory review, Python code; More Rolling Hashes (for Rabin Karp) 4 Sorting 4.1 Lecture 8, Sorting I: Heaps 4.2 Recitation 8, Overview of Sorting Methods; Heaps as Data Structures: Principles, Sorting, Priority Queues 4.3 Lecture 9, Sorting II: Heaps 4.4 Lecture 10, Sorting III: Lower Bounds, Linear-Time Sorting 4.5 Recitation 9, Quiz Review: Interesting Problems 4.6 Lecture 11, Sorting IV: Stable Sorting, Radix Sort 4.7 Recitation 10, Counting,Radix and Bucket Sorting, Gas simulation 5 Searching 5.1 Lecture 12, Searching I: Graph Search, Representations, and Applications 5.2 Lecture 13, Searching II: Breadth-First Search and Depth-First Search 5.3 Lecture 14, Searching III: Topological Sort and NP-completeness 5.4 Recitation 12, BFS and DFS 6 Shortest Paths 6.1 Lecture 15, Shortest Paths I: Intro 6.2 Recitation 13, Assistance for PS 6.3 Lecture 16, Shortest Paths II: Bellman-Ford 6.4 Recitation 14, Generic Shortest-Path Algorithm: Concepts, Properties; Bellman-Ford: Examples, Negative-Cost Cycles 6.5 Lecture 17, Shortest Paths III: Dijkstra 6.6 Recitation 15, Hands-on Dijkstra: Pseudocode, Preconditions, Examples, Why It Works; Priority Queues: Review, Extended Python Implementation 6.7 Lecture 18, Shortest Paths IV: Dijkstra Speedups 6.8 Recitation 16, Array implementation of Dijkstra 7 Dynamic Programming 7.1 Lecture 19, Dynamic Programming I: Memoization, Fibonacci, Crazy Eights, Guessing 7.2 Recitation 17, Hands-on Dynamic Programming: Big Ideas, Memoization in Fibonacci, Crazy Cards, Dijkstra and Bellman Ford Algorithm as dynamic Programming 7.3 Lecture 20, Dynamic Programming II: Longest Common Subsequence, Parent Pointers 7.4 Recitation 18, More Dynamic Programming: Beating Super Mario Bros, Getting Points Back on Tests (LCS), Crazy Eights 7.5 Lecture 21, Dynamic Programming III: Text Justification, Parenthesization, Knapsack, Pseudopolynomial Time, Tetris Training 7.6 Recitation 19, Even More Dynamic Programming: Maxiumum-sum Sub-array, Pwning at Tetris 7.7 Lecture 22, Dynamic Programming IV: Piano Fingering, Structural DP (Trees), Vertex Cover, Dominating Set, Beyond 7.8 Recitation 20, Knapsack and Its Variants, Structural Dynamic Programming: Covering a Tree with Templates, Dominating Set 8 Numerics 8.1 Lecture 23, Numerics I 8.2 Recitation 21, Dynamic Programming Practice: Live Python Coding, Dominating Sets, Structural Dynamic Programming: Covering a Tree with Templates 8.3 Lecture 24, Numerics II 8.4 Recitation 22(1)(2), Divide and Conquer vs Dynamic Programming on Problems: Matrix Multiplication, Tower, Max-sum Subarray, Closet Pair 8.5 Recitation 22(3)(4), Numerics Review, Strassen's Algorithm for Matrix Multiplication 9 Beyond 6.006 9.1 Lecture 25, Beyond 6.006: Follow-on Classes, Geometric Folding Algorithms 9.2 Recitation 23, Review for the Final Exam

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

• partial python code for 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
  • Problem statement and original solution [PDF]
  • Victor's solution during the quiz [PDF] (read and stop complaining about long psets :P)
• 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)
  • Square Root of 2 [XHTML/JS]
  • Chord Length [XHTML/JS]
  • Source code [Zip]

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):
  • Matrix Chain Multiplication [Zip]
  • Longest Zig-Zag Subsequence [Zip]
• 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

• Hueihan's Slides [PDF] |
• MaxSumSubarray[PDF]

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]