Erik Demaine
Professor of Electrical Engineering and Computer Science · MIT · MacArthur Fellow · author of Geometric Folding Algorithms
MIT Professor of Computer Science and MacArthur Fellow renowned for algorithmic data structures, computational origami, and hardness proofs.
- lectures
- 51
- series
- 3
- hours
- 61
Start here
Series and courses
MIT 6.046J: Design and Analysis of Algorithms
Open the course
- 1Course Overview, Interval Scheduling
- 2Divide & Conquer: Convex Hull, Median Finding
- 3Divide & Conquer: FFT
- 4R2. 2-3 Trees and B-Trees
Show 11 moreShow fewer
- 5Divide & Conquer: Van Emde Boas Trees
- 6Amortization: Amortized Analysis
- 7Randomization: Matrix Multiply, Quicksort
- 9Randomization: Universal & Perfect Hashing
- 10Augmentation: Range Trees
- 12Dynamic Programming: All-Pairs Shortest Paths
- 13Greedy Algorithms: Minimum Spanning Tree
- 18Complexity: P, NP, NP-completeness, Reductions
- 20Complexity: Fixed-Parameter Algorithms
- 26Cache-Oblivious Algorithms: Medians and Matrices
- 27Cache-Oblivious Algorithms: Searching & Sorting
MIT 6.851: Advanced Data Structures
Open the course
- 1Persistent Data Structures
- 2Retroactive Data Structures
- 3Geometric Structures I
- 4Geometric Structures II
Show 18 moreShow fewer
- 5Dynamic Optimality I
- 6Dynamic Optimality II
- 7Memory Hierarchy Models
- 8Cache-Oblivious Structures I
- 9Cache-Oblivious Structures II
- 10Dictionaries
- 11Integer Models
- 12Fusion Trees
- 13Integer Lower Bounds
- 14Sorting in Linear Time
- 15Static Trees
- 16Strings
- 17Succinct Structures I
- 18Succinct Structures II
- 19Dynamic Graphs I
- 20Dynamic Graphs II
- 21Dynamic Connectivity Lower Bound
- 22History of Memory Models
MIT 6.006: Introduction to Algorithms
Open the course
- 2Models of Computation, Random Access Machine & Document Distance
- 5Binary Search Trees & Runway Reservation Scheduling
- 6AVL Trees, Tree Rotations & Guaranteed O(log n) Height
- 7Decision-Tree Ω(n log n) Lower Bound, Counting Sort & Radix Sort
Show 10 moreShow fewer
- 8Hashing with Chaining, Simple Uniform Hashing & Universal Families
- 9Table Doubling, Karp-Rabin
- 13Breadth-First Search (BFS)
- 14Depth-First Search (DFS), Topological Sort
- 19Dynamic Programming I: Fibonacci, Shortest Paths
- 20Dynamic Programming II: Text Justification, Blackjack
- 21Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- 22Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
- 23Computational Complexity
- 24Topics in Algorithms Research
In these lectures
- Small changes in problem constraints can shift an algorithm from polynomial-time tractability to NP-completeness.Course Overview, Interval Scheduling
- Polynomial multiplication is equivalent to vector convolution and can be solved in time using the Fast Fourier Transform.Divide & Conquer: FFT
- Breadth-First Search (BFS) systematically explores graphs level by level, finding the shortest path (fewest edges) in unweighted graphs.Breadth-First Search (BFS)
Draws on
People cited in the lectures, at the moment of the citation.
- Peter van Emde BoasCo-author of the van Emde Boas data structure.
- Richard BellmanInventor of dynamic programming and the Bellman-Ford algorithm, cited for the origin of the term.
- Martin Farach-ColtonCo-author on cache-oblivious B-trees and simplifications of old data structures around 2001.
- van Emde BoasInvented van Emde Boas trees, referenced for drawing similar tree pictures.
- Harold ProkopM.Eng. thesis on cache-oblivious static search trees
- Eric PriceCo-author of a paper originating from a class open problem session four years prior
Playlists
2Taught with
Same subject, Algorithms & Theoretical CS
Connections
62Their places, courses, books and lectures.
Scholars2
Institutions2
Courses3
Lectures51
- Course Overview, Interval Scheduling
- Divide & Conquer: FFT
- Breadth-First Search (BFS)
- Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Complexity: P, NP, NP-completeness, Reductions
- Randomization: Universal & Perfect Hashing
Show 45 moreShow fewer
- Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
- Dynamic Programming I: Fibonacci, Shortest Paths
- Persistent Data Structures
- Randomization: Matrix Multiply, Quicksort
- Depth-First Search (DFS), Topological Sort
- Amortization: Amortized Analysis
- Dictionaries
- Dynamic Graphs I
- Table Doubling, Karp-Rabin
- Integer Models
- Static Trees
- Divide & Conquer: Convex Hull, Median Finding
- Geometric Structures I
- Divide & Conquer: Van Emde Boas Trees
- Strings
- Greedy Algorithms: Minimum Spanning Tree
- History of Memory Models
- Augmentation: Range Trees
- Dynamic Programming: All-Pairs Shortest Paths
- R2. 2-3 Trees and B-Trees
- Complexity: Fixed-Parameter Algorithms
- Dynamic Connectivity Lower Bound
- Integer Lower Bounds
- Fusion Trees
- Dynamic Graphs II
- Succinct Structures I
- Retroactive Data Structures
- Binary Search Trees & Runway Reservation Scheduling
- Dynamic Optimality II
- Cache-Oblivious Structures I
- Memory Hierarchy Models
- Dynamic Programming II: Text Justification, Blackjack
- Sorting in Linear Time
- Hashing with Chaining, Simple Uniform Hashing & Universal Families
- Cache-Oblivious Algorithms: Medians and Matrices
- Geometric Structures II
- Decision-Tree Ω(n log n) Lower Bound, Counting Sort & Radix Sort
- Cache-Oblivious Algorithms: Searching & Sorting
- Cache-Oblivious Structures II
- Computational Complexity
- Succinct Structures II
- Dynamic Optimality I
- AVL Trees, Tree Rotations & Guaranteed O(log n) Height
- Models of Computation, Random Access Machine & Document Distance
- Topics in Algorithms Research









