In the Graduate Algorithms course I'm currently taking we've been learning a lot about Fast Fourier Transforms and divide-and-conquer algorithms for conducting them. Although I've known about FFT at the highest-levels (like that you might use it to isolate frequencies from a signal), this is the first time I've had to learn about it in-depth and I've found it pretty challenging. Thankfully there are lots of resources on the subject online if you know where to find them. And that's a big if.
This post is my attempt at aggregating some of the resources I found particularly helpful. They're listed in order of requiring the least prerequisite knowledge to the most.
What is a Fast Fourier Transform?
The lectures and textbook for my class tackled FFT from primarily a mathematical perspective and I found it difficult to understand the how it helped in practice. The following video from 3 Blue 1 Brown really helped explain it to me at this high level:
Understanding What Are the Nth Roots of Unity
Another thing I had trouble with was understanding the Nth Roots of Unity. With my weaker match background I did not have much exposure to the complex plane and I honestly don't think I had ever heard the term "Roots of Unity." Well it turns out they're pretty important for FFT and a lot of resources consider them to be prerequisite knowledge. I found the following video helpful for getting me on the same page:
Doing Fourier Transforms by Hand
The next thing I found useful was a step-by-step guide of how you might use Fourier Transforms to multiply two polynomials by hand. Most examples explain generalized solutions to the problem using variables and don't actually explain using concrete examples. Someone shared the following StackExchange post with me and I found it was just what I needed.
Lectures for Understanding FFT by Divide-and-Conquer
Lastly, I watched some lectures from other programs to see the material explained in different ways. I found this lecture by Erik Demaine useful, but only after digesting some of those other resources I mentioned earlier.
I also found these lectures from a different Georgia Tech class (CS 6505: Computability, Complexity & Algorithms), but I believe you'll need to create a free Udacity account to view them.
Summary
I typically prefer explaining topics on my own (see my Solving the Knapsack Problem with Dynamic Programming post) to solidify my own understanding, but for this one I'm still working through that bit myself! Again, I've found this list of resources helpful and hopefully by recording it all in one place it will be easier for other folks (myself included) to find in the future.
Top comments (0)