In this lecture, we wrap up our discussion of divide and conquer algorithms by talking about how to efficiently perform convolution via the Fast Fourier Transform (FFT).
Timestamps:
00:00 Introduction
00:31 Karatsuba Multiplication
03:52 Convolution
07:53 Fast Fourier Transform
10:47 Convolution Algorithm
11:25 Example
12:03 Conclusion
#fft #convolution #karatsuba #multiplication #divideandconquer #algorithms #fourier #recursion #recurrence #timecomplexity #computerscience
