In the last two posts we understood the basics of fourier transform, how to speed up the DFT calculations with FFT, then looked at how we can use the FFT algorithm to solve different problems such as time series analysis, pattern matching in strings, convolution etc. Part 1 An excursion…