3. Divide & Conquer: FFT
310,767
Published 2016-03-04
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Erik Demaine
In this lecture, Professor Demaine continues with divide and conquer algorithms, introducing the fast fourier transform.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu/
All Comments (21)
-
Just a tip for new viewers: Don't stop!! Continue watching the video, don't expect yourself to understand everything as you go, grab the essence of each section of the video and in the end it is all gonna make sense. If it did not you can always go back but don't quit this video. Amazing job Erik!!!
-
Erik: "I didn't go to high school but I assume in high school you learned this..."
-
Am I the only one really impressed by the quality of that chalk? It never makes those high pitched sounds ... soo smooth
-
I first encountered the FFT derivation of the DFT thirty years ago when I took a digital filters class while a graduate student at Georgia Tech, and I am as bolled-over now as I was then by this most elegant and incredibly useful algorithm. Thank you, Professor Demaine. --
-
The part about how size of X needs to be reduced by 2 when we go to X^2 is just brilliant! That explains the choice of x_k's that I saw on other ppl's implementation so well!
-
Not going to lie, I cam here to learn the FFT as an engineering student, but stuck around to learn about this CS time complexity.
-
This is the best overview of what FFT is, brilliant teacher!
-
Amazing to see that such a brilliant guy can also be a brilliant educator. From my experience this is pretty rare!
-
These tattoo jokes tho. BRILLIANT!
-
Professor makes his lecture seems the learning material is so easy! Thank you!
-
This is THE BEST FFT lecture ever. Erik is simply awesome!
-
Real men cried at the end when he brought up those applications. Truly beautiful mathematics
-
My Brain Stack starts overflowing after 35:00.
-
Its always a pleasure to listen Eric's lecture. Great professor.
-
One of the best lectures I've seen :) really brings out the true nature of the DFT
-
As he puts it, this all was "very cool, very cool". Thanks, Erik.
-
This guy oozes brilliance! Amazing lecture!
-
this lecture is freaking amazing
-
27:46, we can use Lagrange's Formula to compute Coefficients from Samples. It is O(n^2) but avoids inverse computation by Gaussian Elimination.
-
Throughout the whole video i could not stop wondering about him(he is a child prodigy, became a professor at MIT at 20 )
