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!!!
@chill6962
2 жыл бұрын
Thank you
@migueld2456
2 жыл бұрын
This is very wise advise.
@__dekana__
Жыл бұрын
Thank you
@AnthosPhotos
7 ай бұрын
I followed the strategy and now reading this comment. Going to advise the same
@mrisholukamba1696
3 ай бұрын
Thank youu, I rewatched 3 times before i actually got it. And I think i will rewatch for the 4th time to understand more on execution time complexity and some concepts which were mentioned but not explained enough
@junweima
6 жыл бұрын
Erik: "I didn't go to high school but I assume in high school you learned this..."
@rj-nj3uk
5 жыл бұрын
Students:"hahahaha"
@godfather5557
5 жыл бұрын
convolution: 12:46
@m322_yt
3 жыл бұрын
@@julius333333 and yet he’s such a humbling, sympathetic person
@tsunghan_yu
3 жыл бұрын
8:56
@hemiacetal1331
2 жыл бұрын
Weird flex but it hurts
@personanongrata987
Жыл бұрын
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. --
@abdulelahaljeffery6234
7 жыл бұрын
This is the best overview of what FFT is, brilliant teacher!
@mario7501
3 жыл бұрын
Amazing to see that such a brilliant guy can also be a brilliant educator. From my experience this is pretty rare!
@netoskin
Ай бұрын
This is the best explanation of the FFT you can find very intuitive and step by step. Most people explain the FFT with a matrix of coefficients and I just never understood it until I saw this more algorithm oriented explanation
@henrytay1706
2 жыл бұрын
Professor makes his lecture seems the learning material is so easy! Thank you!
@skyzhangty1
3 жыл бұрын
This is THE BEST FFT lecture ever. Erik is simply awesome!
@yashjakhotiya5808
5 жыл бұрын
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.
@tibortresla
8 жыл бұрын
These tattoo jokes tho. BRILLIANT!
@TW0T0NGUE
7 жыл бұрын
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.
@tennma6250
4 жыл бұрын
same here haha
@woosix7735
Жыл бұрын
Kinda the whole point of the fft
@mavenuparker
7 жыл бұрын
Didn't know that Jin from SamuraI Champloo now teaches at MIT. Thanks for the amazing overview of FFT. Amazing lecture
@SR-kp8zu
4 жыл бұрын
lmaooo did not expect to see a samurai champloo reference while learning about the FFT
@andrestifyable
5 жыл бұрын
Am I the only one really impressed by the quality of that chalk? It never makes those high pitched sounds ... soo smooth
@hektor6766
5 жыл бұрын
It's called railroad chalk. Made with calcium sulfate (gypsum), not calcium carbonate (chalk). Softer than chalk hence bolder lines and no screech. Dustier though, so treated with a dust inhibitor, that's why the surface of the stick is yellow but it writes in white.
@matthewquinn5192
4 жыл бұрын
I didnt want to watch this video because i hate that sound so much, thank you for the reassurance so i can watch without fear
@vishalvibes_
4 жыл бұрын
Is it hagoromo?
@henrypeterson8497
2 жыл бұрын
@@vishalvibes_ nope
@vamsimohan5369
3 жыл бұрын
Throughout the whole video i could not stop wondering about him(he is a child prodigy, became a professor at MIT at 20 )
@nalcow
Жыл бұрын
Its always a pleasure to listen Eric's lecture. Great professor.
@suicide_king6804
6 жыл бұрын
Having barely mastered some basic arithmetic, this may be a little advanced...even though I have no idea wtf this guy is talking about/drawing, it is fascinating to try and understand it.
@BenjaminKorenBJK
5 жыл бұрын
@@aristosgeorgiou6060 yeah, very relatable, lol
@karanveersingh5535
2 жыл бұрын
@@aristosgeorgiou6060 lol 🤣
@saicharanmarrivada5077
2 жыл бұрын
@@aristosgeorgiou6060lol😂
@sanatanshrivastava1725
2 жыл бұрын
As he puts it, this all was "very cool, very cool". Thanks, Erik.
@akshaydarekar5863
5 жыл бұрын
My Brain Stack starts overflowing after 35:00.
@jayhoeliotdecabrio4050
3 жыл бұрын
Erik: "I didn't go to high school but I assume in high school you learned this..." reminds me seldon cooper
@aSeaofTroubles
7 жыл бұрын
One of the best lectures I've seen :) really brings out the true nature of the DFT
@szyszkienty
3 жыл бұрын
This guy oozes brilliance! Amazing lecture!
@sa6opopov
7 ай бұрын
This is the most beautiful algorithm I have seen
@chethankumar4303
6 жыл бұрын
Gave an in depth understanding of FFT...Brilliant Explanation
@programmingbro2424
3 жыл бұрын
this lecture is freaking amazing
@martinstefcek4089
6 жыл бұрын
The root representation should be (x-r1)...(x-r(n-1)) not from (x-r0), you can easily see that if you do it from r0, then you will have polynomial of x^n (which is one degree higher than what he used in the first rep.)
@sophiophile
3 жыл бұрын
He did this because he claimed you need n points to represent an n-1 polynomial. If you watch later into the video, he wrote it in this weird way cuz he was centring things around the number of points you need, not the number of coefficients represent the polynomial.
@TheBoutchard
4 жыл бұрын
Me: Has a school assignment where I have to implements an algorithm dividing two polynomials and I have no idea what to do This man: I'm about to save this man whole career
@bhaskarpandey8586
3 жыл бұрын
Modify euclidean algorithm for gcd
@MaxMarrone
5 жыл бұрын
Okay, we've figured out how to convert between different representations of polynomials, but how do we go from there to the familiar application of the FFT - converting between the time domain and frequency domain? Given a bunch of samples, we want a weighted sum of sinusoids, but what we get here is the coefficients of a polynomial.
@sophiophile
3 жыл бұрын
This question has been plaguing me for a while. Did you ever discover an answer to this.
@THeMin1000
3 жыл бұрын
@@sophiophilethe coefficients that we get IS the FT, instead of the points being the coefficients of the polynomial representing the time domain function we get the samples from the polynomial representing the polynomial in frequency domain.
@madhukiranattivilli2321
2 жыл бұрын
Implemented FFT algo for both polynomial multiplication and integer multiplication Deadly algo :) % java FFTPolynomialMultiplication i/p polynomial A : 2 + 3x + xˆ2 i/p polynomial B : 1 + 2xˆ2 n (=2ˆk) = 8 o/p polynomial C : 2 + 3x + 5xˆ2 + 6xˆ3 + 2xˆ4 % java FFTPolynomialMultiplication i/p polynomial A : 8 + 7xˆ2 + 3xˆ3 + 9xˆ5 i/p polynomial B : 4 + 5x + 6xˆ2 + 7xˆ3 + 8xˆ4 n (=2ˆk) = 16 o/p polynomial C : 32 + 40x + 76xˆ2 + 103xˆ3 + 121xˆ4 + 103xˆ5 + 122xˆ6 + 78xˆ7 + 63xˆ8 + 72xˆ9 % java FFTIntegerMultiplication i/p integers : A = 123,456,789 B = 956,227,496 n = 32 product = 118,052,776,209,670,344 % java FFTIntegerMultiplication i/p integers : A = 2,147,483,647 B = 2,147,483,647 n = 32 product = 4,611,686,014,132,420,609
@kittel-dev
3 жыл бұрын
This was hard. Hope i will understand it soon.
@noguide
5 жыл бұрын
*Stands up & claps* Eric, take a bow. This should be the reference for any instructor of how to explain the FFT.
@Kaslor1000
5 жыл бұрын
Phenomenal lecture.
@nikhil_kolla_12
5 жыл бұрын
Excellent explanation.
@c0t556
5 жыл бұрын
This guy is so cool
@vivekdabholkar5965
Жыл бұрын
Nice lecture! I thought MIT classes would be very hard.
@BTDiLmarinen
Жыл бұрын
MIT isn't a place for geniuses, it's just a normal university that only accepts students that can apply themselves.
@off4on
4 жыл бұрын
I think he meant V\Y not V\A at around 29:00...
@junzhai1715
3 жыл бұрын
i think so too
@roushankumar-lu2ov
5 жыл бұрын
I'm in third semester,but this particular video seems to much difficult ,there are so many things in this I don't know
@chinmaydas4053
3 жыл бұрын
Sir what is the best programming language for analysis and design of data structures and algorithms??...
@sakules
5 жыл бұрын
wonderful teacher
@LydellAaron
2 жыл бұрын
53:06, 57:15 takes a moment to give tau some respect. Big flex 💪
@saltcheese
5 жыл бұрын
if there is a god, MIT is doing her work
@hektor6766
5 жыл бұрын
I was just thinking earlier today about root 2/2 being the sine and cosine of 45 degrees, e^(2)i pi (e^i tau) and how they related to the unit square and circle. Fourier, Gauss, Dirichlet all stood on Euler's shoulders.
@englishmotherfucker1058
4 жыл бұрын
it always comes back to euler like it's rome all roads, somewhere, somehow, all lead to euler
@paragggoyal1552
Жыл бұрын
at last, absolute detail!
@abugigi
Жыл бұрын
Erik is Demaine man!
@shivamp5410
8 ай бұрын
Why do we still have x elements when we split the set and each part has n/2? I'm a bit confused on this part any help would be appreciated. Thanks.
@iamshadmirza
7 жыл бұрын
This guy is amazing
@rosenzhang1704
5 жыл бұрын
why we must take the nth root of unity, cant we take like -1, 1, -2, 2 ....as X? This will also collapse?
@elliotwaite
5 жыл бұрын
Squaring those numbers will give you 1, 1, 4, 4, giving you the set {1, 4} (a collapse of 4 numbers to 2), but if you square those again you get {1, 16}, which doesn't collapse the set any further. You need the collapsed set to collapse again when you square each value a second time, and then collapse again when you square the numbers a third time, and so on, hence the complex numbers. You could use the nth roots of any number, but using the nth roots of 1 is simpler and lends the alternative representation to represent amplitude and phase information in frequency space. If you used the nth roots of another number I don’t think the alternative representation could be interpreted the same way.
@haardshah1676
4 жыл бұрын
@@elliotwaite 1:07:35 if the complex conjugate is just minus the power in the exponential, why did he write exp(-ijkT/n/n)? why the divide by n divide by n (again)? is it a mistake? (also sorry I asked as subcomment; I thought it'd get lost in the clutter otherwise)
@elliotwaite
4 жыл бұрын
@@haardshah1676 it looks like the second division by n was a mistake. He realizes this soon after writing it and erases it. Does that answer your question?
@stefanosmakris5641
4 жыл бұрын
This was AWESOME! Thank you!
@Harish-ou4dy
4 ай бұрын
whats the deal with those frizbees?
@erans0496
2 жыл бұрын
Erik: " I didn't go to high school, but I assume in high school algebra you learn this...." Me: Drop from CS and cry...
@not_melkor
3 жыл бұрын
This is what reaching GOD Level feels like in teaching?
@MrAwesomeaditya
4 жыл бұрын
is it just me or does he look like post malone had a studious brother
@pepehimovic3135
11 ай бұрын
Let me guess, it involves powers of 2?
@5daydreams
6 ай бұрын
is there a followup to this lecture?
@mitocw
6 ай бұрын
Here's the recitation that followed the lecture. Linking to it from the playlist: kzitem.info/news/bejne/tYWYl6irfoxji2k&pp=iAQB. We hope this is what you are looking for.
@RSPSupply
6 жыл бұрын
Great Job!
@aayushbajaj2260
Жыл бұрын
holy crap, the tau thing
@shivanandt4532
6 жыл бұрын
@42.00, should not that be O(n^3) as we have total work = n + 2n + 4n + ...+ n*n = n ( 1 + 2 ...+n) = n*n*(n+1)/2 = O(n^3), he says it is O(n^2)
@abdu1998a
6 жыл бұрын
actually you are wrong. It is a simple mistake n+ 2n +4n + 8n ... n*n = n( 1+ 2+ 4+ 8...n) and not n(1+2+3+4+5+6....n). Therefore, right part is not n*(n+1)/2. It is geometric series so right part is 2n-1*. Thus, it is O(n^2). * a^0 + A^1 .... a^k = a^(k+1)-1/a-1 in this case a = 2 and a^k = n.
@kittel-dev
3 жыл бұрын
44:00 in this moment, all the other stuff about fft made a little more sense :-)
@roadracer1593
3 күн бұрын
Dude. I admire your hair. I'm jealous. All my hair is falling out. I'll be bald soon.
@wtw5002
3 жыл бұрын
"Screw Pi" - omg i nearly died. That was hilarious. I deeply regret my decision to avoid STEM classes in high school and college. That was a terrible mistake.
@ka1wht
3 жыл бұрын
It’s not too late to learn. Think of the ones you regret not taking and either purchase a book or take a class. One of the greatest things about our minds is that they are malleable.
@fatihcihanhizlikan1427
6 жыл бұрын
I loved this video.
@andrewolesen8773
6 жыл бұрын
So is the Nfft value for the FFT function in the matlab signal analyzer app the same as the 'n value rounded to the next largest power of 2' he talks about in the video?
@ezzoalgaddafy5934
Жыл бұрын
Is it too complex or just a first impression?
@woosix7735
Жыл бұрын
I like this guy
@bryanlozano8905
2 жыл бұрын
Dude, why are you erasing the chalkboard before I finish taking notes?
@rodacoram
Жыл бұрын
Is divide and conquer a genetic algorithm?
@everaldoantoniomoreiraalve1023
10 ай бұрын
Amazing!
@haardshah1676
4 жыл бұрын
1:07:35 if the complex conjugate is just minus the power in the exponential, why did he write exp(-ijkT/n/n)? why the divide by n divide by n (again)? is it a mistake?
@willlenk862
2 жыл бұрын
Because he's trying to invert the V-matrix which requires a complex conjugate operation and then a divide by n. Note he later corrected the division by n (because the magnitude of the xk values must be 1), and deferred it to after the matrix multiplication
@BuiDucLoc419
4 жыл бұрын
Best lecture
@ilyboc
4 жыл бұрын
55:13 This should be squared no?
@kaustavguharoy4532
2 жыл бұрын
Marvellous
@MauriceMauser
3 ай бұрын
💥 when Marty McFly arrives in 1965 💥
@kaushiksurikuchi
6 жыл бұрын
Erik, the best
@HeisenbergHK
Жыл бұрын
How can i find the full playlist?
@mitocw
Жыл бұрын
Every MIT OpenCourseWare course on KZitem has a playlist. They are named by the course. In this case, the playlist is "MIT 6.046J Design and Analysis of Algorithms, Spring 2015" kzitem.info/door/PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp. Every video we publish has the course name and number in the video description. Best wishes on your studies!
@udomatthiasdrums5322
4 жыл бұрын
love it!!
@dianamartinez6071
4 жыл бұрын
if you want to multiply two polynomials, why not just evaluate both of them, and then just multiply de results??
@haardshah1676
4 жыл бұрын
That would only result in a singular value. The goal is to multiply two polynomials to output another polynomial.
@nitishsandhu4462
8 жыл бұрын
I think there is one mistake at 15:36, when he wrote down samples to represent a polynomial of degree n. He took n samples to represent a polynomial of degree n uniquely. But this is untrue, to represent a polynomial of degree n, we need at least n+1 sample points, for all different x points.
@Davissb1aine
8 жыл бұрын
The polynomial is of degree n-1: (1 + x + ... + x^(n-1)). Therefore, you need n sample points to uniquely represent this polynomial.
@paragggoyal1552
Жыл бұрын
you look so excited just wait till i hit you, you will be less excited. LOL at 15:40
@dianamartinez6071
4 жыл бұрын
In what minute did you get lost?
@englishmotherfucker1058
4 жыл бұрын
last lecture, actually just wandering around from there well I actually got lost in 6.006
@distrologic2925
3 жыл бұрын
TAU IS A WHOLE CIRCLE
@xinli6243
5 жыл бұрын
Can someone explain why at 40:16 the last item is O(n + |x|)? Where does this n come from? I think it should be O(|X|) because once we get Aeven(x) and Aodd(x) for any x in X, it just constant time to compute Aeven(x) + x*Aodd(x) for each x. Now we have |X| points to computer, so it takes |X| time to get A(x) for x in X. Correct me if I am wrong
@kyawshinthant4237
2 жыл бұрын
This is a very late comment but I'm posting so that other people can see. I think that n comes from creating the two coefficient vectors for the two polynomials A_even and A_odd by linearly scanning the coefficient vector of the polynomial A.
@VSN1001
2 жыл бұрын
I love how he advocates for tau with so much passion he got a tattoo!
@VSN1001
2 жыл бұрын
And yes I support tau!
@rownadoherty
2 жыл бұрын
Well... a "tattoo" using a laser-jet printer and a temporary tattoo kit.
@_HarshVerma
2 жыл бұрын
"I didn't go to high school but I assume in high school you learned this" you dont have to flex like eric :(
@뭐하지오늘하루는
5 жыл бұрын
9:54 can anybody why it is O(n^2) ?
@뭐하지오늘하루는
5 жыл бұрын
nvm, i was dumb. it was n term times n terms so it should be n^2
@hmedgmal1364
Жыл бұрын
From Algeria 🇩🇿🇩🇿🇩🇿🇩🇿🇩🇿🇩🇿
@DarwinsBuddy
8 жыл бұрын
cool! free frisbees@MIT
@u2bacount
2 жыл бұрын
that MIT chalk...
@rakeshlal6882
5 жыл бұрын
kudos to camera person for zooming out at 26:14 .
@constipatedlecher
Жыл бұрын
I miss blackboards.
@alpacino3989
5 жыл бұрын
terrence tao
@abrorabyyu6221
Жыл бұрын
come from veritasium
@JohnSikes73
4 жыл бұрын
If I was taking this course, I'd have owned O(n) frisbees by the end of the course (n is number of classes). :p
@blykgod
4 жыл бұрын
Am I the only one who thinks the Ck is wrong at 9:25
@shahar963
7 жыл бұрын
why does MIT still use chalkboards?
@gillianseed4419
7 жыл бұрын
its so they can spend money on important research like finding gods number for a rubics cube
@Originalimoc
6 жыл бұрын
Because it's good.
@loganwishartcraig
6 жыл бұрын
Pacing. It also allows students to take notes on paper which has been found to improve cognitive processing.
@iAkOu1
7 жыл бұрын
Damn, you too? I like ε so much I tattoo it on my boobs.
@naimsantos2430
4 жыл бұрын
53:06 wowwwwww lol
@yuensc196
4 жыл бұрын
life sucks
@spirridd
7 жыл бұрын
Where is FFT explained?
@danielf9110
7 жыл бұрын
it is the recursive calculation of Aeven(x^2), Aodd(x^2) when selecting the propper x's as shown in the video.
@Pietrabentivi
7 жыл бұрын
@tchappyha4034
5 жыл бұрын
This algorithm is a wonderful algorithm, but it is just a typical divide and conquer algorithm. This algorithm is the same algorithm as merge sort algorithm from the algorithm design point of view. Nothing new. Why did he give a lecture on this algorithm in "Design and Analysis of Algorithms"? He could give this lecture in "Introduction to Algorithms".
Пікірлер: 209