Lectures and Recitations

From 6.006 Introduction to Algorithms

Jump to: navigation, search


Introduction and Document Distance

Lecture 1, Introduction and Document Distance

Recitation 1, Document Distance in Python (docdist{1,2,3,4}.py)

Lecture 2, More Document Distance, Mergesort

Recitation 2, Python Cost Model, Review for Asymptotic Notation & Mergesort

Binary Search Trees

Lecture 3, Airplane scheduling; Binary Search Trees

Recitation 3, Binary Search Trees

Lecture 4, Balanced Binary Search Trees

Recitation 4, AVL Trees (Balanced Binary Search Trees)


Lecture 5, Hashing I: Chaining, Hash Functions

Recitation 5, Hashing in Python, Mutability

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

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)


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

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

Lecture 11, Sorting IV: Stable Sorting, Radix Sort

Recitation 10, Counting,Radix and Bucket Sorting, Gas simulation

  • Hueihan's Slides [PDF]


Lecture 12, Searching I: Graph Search, Representations, and Applications

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

Shortest Paths

Lecture 15, Shortest Paths I: Intro

  • Reading: CLRS, Chapter 24 (Intro)

Recitation 13, Assistance for PS

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

Lecture 18, Shortest Paths IV: Dijkstra Speedups

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

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

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

Lecture 22, Dynamic Programming IV: Piano Fingering, Structural DP (Trees), Vertex Cover, Dominating Set, Beyond

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


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):
    • 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

Beyond 6.006

Lecture 25, Beyond 6.006: Follow-on Classes, Geometric Folding Algorithms

Recitation 23, Review for the Final Exam

Personal tools