3. Divide & Conquer: FFT

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
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

[KaushikMishrakk]

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!!!

[junweima]

Erik: "I didn't go to high school but I assume in high school you learned this..."

[andrestifyable]

Am I the only one really impressed by the quality of that chalk? It never makes those high pitched sounds ... soo smooth

[leminhphuct]

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!

[personanongrata]

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.

--

[mario]

Amazing to see that such a brilliant guy can also be a brilliant educator. From my experience this is pretty rare!

[henrytay]

Professor makes his lecture seems the learning material is so easy! Thank you!

[TWTNGUE]

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.

[abdulelahaljeffery]

This is the best overview of what FFT is, brilliant teacher!

[skyzhangty]

This is THE BEST FFT lecture ever. Erik is simply awesome!

[nalcow]

Its always a pleasure to listen Eric's lecture. Great professor.

[aSeaofTroubles]

One of the best lectures I've seen :) really brings out the true nature of the DFT

[yashjakhotiya]

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.

[szyszkienty]

This guy oozes brilliance! Amazing lecture!

[sanatanshrivastava]

As he puts it, this all was "very cool, very cool".
Thanks, Erik.

[akshaydarekar]

My Brain Stack starts overflowing after 35:00.

[randomperson]

Real men cried at the end when he brought up those applications. Truly beautiful mathematics

[mavenuparker]

Didn't know that Jin from SamuraI Champloo now teaches at MIT.

Thanks for the amazing overview of FFT. Amazing lecture

[chethankumar]

Gave an in depth understanding of FFT...Brilliant Explanation

[muhammedafifi]

I don't know how I used to call myself an engineer before watching this video!