Data Structures and Algorithms |
12 Fast Fourier Transforms |
Fourier transforms have wide application in scientific and engineering problems, for example, they are extensively used in signal processing to transform a signal from the time domain to the frequency domain.
Here, we will use them to generate an efficient solution to an apparently unrelated problem - that of multiplying two polynomials. Apart from demonstrating how the Fast Fourier Transform (FFT) algorithm calculates a Discrete Fourier Transform and deriving its time complexity, this approach is designed to reinforce the following points:
Because of the limitations of HTML in handling mathematical equations, the notes for this section were prepared with LaTeX and are available as a PostScript file.
Continue on to Hard Problems | Back to the Table of Contents |