Home

Course Information

Calendar

Lectures and Recitations

Problem Sets

Quizzes

Resources

Previous terms

- Introduction
- Lecture 1, Introduction and Document Distance (source code and a relevant remark about python. ) Please use nb to jot down any questions you have or improvements you'd like to suggest on the notes; I'll be responding to what's posted there.
- Recitation 1, Python Introduction and Asymptotic Complexity Review
- Lecture 2, Peak Finding Problem
- Recitation 2, Peak Finding Problem

- Binary Search Trees
- Lecture 3, Scheduling and Binary Search Trees
- Recitation 3, Binary Search Trees
- Lecture 4, Balanced Binary Search Trees
- Recitation 4, AVL Trees (demo applet)

- Hashing
- Lecture 5, Hashing I : Chaining, Hash Functions
- Recitation 5, Hashing I
- Lecture 6, Hashing II : Table Doubling, Rolling Hash of Karp and Rabin
- Recitation 6, Hashing II
- Lecture 7, Hashing III : Open Addressing

- Sorting
- Lecture 8, Sorting I : Insertion Sort, Merge Sort, Master Theorem
- Lecture 9, Sorting II : Heaps
- Lecture 10, Sorting III: Lower Bounds, Counting Sort, Radix Sort

- Graphs and Search
- Lecture 11, Searching I: Graph Search and Representations
- Lecture 12, Searching II: Breadth-First Search and Depth-First Search (reading notes)
- Lecture 13, Searching III: Topological Sort
- Lecture 14, Shortest Paths I: Intro
- Lecture 15, Shortest Paths II: Bellman-Ford
- Lecture 16, Shortest Paths III: Dijkstra and Special Cases
- Lecture 17, Shortest Paths IV: Speeding Up Dijkstra (and Wagner paper with additional tricks)

- Dynamic Programming
- Lecture 18, Dynamic Programming I: Memoization, Fibonacci, Crazy Eights
- Lecture 19, Dynamic Programming II: Shortest Paths, Longest Common Subsequence, Parent Pointers
- Lecture 20, Dynamic Programming III: Text Justification, Knapsack, Pseudopolynomial Time
- Lecture 21, Dynamic Programming IV: Piano Fingering, Structural DP (Trees), Vertex Cover, Dominating Set, Treewidth

- Numerics
- Lecture 22, Numerics I
- Lecture 23, Numerics II
- Lecture 24, Numerics III

- NP-completeness
- Lecture 25, NP-completeness

- Conclusion
- Lecture 26