1. Course Overview, Interval Scheduling
1:23:342. Divide & Conquer: Convex Hull, Median Finding
1:20:34R1. Matrix Multiplication and the Master Theorem
53:463. Divide & Conquer: FFT
1:20:52R2. 2-3 Trees and B-Trees
30:454. Divide & Conquer: van Emde Boas Trees
1:20:145. Amortization: Amortized Analysis
1:15:536. Randomization: Matrix Multiply, Quicksort
1:21:52Lecture 7: Randomization: Skip Lists (6.046J)
1:20:56Lecture 8: Randomization: Universal & Perfect Hashing (6.046J)
1:21:51Lecture 9: Augmentation: Range Trees (6.046J)
1:24:34Lecture 10: Dynamic Programming: Advanced DP (6.046J)
1:20:08Lecture 11: Dynamic Programming: All-Pairs Shortest Paths (6.046J)
1:21:49Lecture 12: Greedy Algorithms: Minimum Spanning Tree (6.046J)
1:22:10Lecture 13: Incremental Improvement: Max Flow, Min Cut (6.046J)
1:22:58Lecture 14: Incremental Improvement: Matching (6.046J)
1:22:32Lecture 15: Linear Programming: LP, Reductions, Simplex (6.046J)
1:22:27Lecture 16: Complexity: P, NP, NP-completeness, Reductions (6.046J)
1:25:253. Divide & Conquer: FFT
Professor Demaine introduces the Fast Fourier Transform (FFT) as a foundational divide and conquer algorithm. The lecture details the algorithm's application to polynomial multiplication, outlining its recursive structure and computational complexity.
MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: http://ocw.mit.edu/6-046JS15
Instructor: Erik Demaine
R1. Matrix Multiplication and the Master Theorem
Next · Lecture 5R2. 2-3 Trees and B-Trees
Seminar notes & discussion
No public seminar notes on this lecture yet.