ConceptTheory & Algos
Fast Fourier transform
An algorithm used to compute the discrete Fourier transform and its inverse.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
6Each in their own terms, from the easiest level.
Ryan O'Donnell
An efficient algorithm to compute the Discrete Fourier Transform in arithmetic operations.Gilbert Strang
An algorithm that computes the discrete Fourier transform and its inverse very quickly, enabling fast change of basis.Erik Demaine & Srini Devadas
A divide and conquer algorithm that computes the discrete Fourier transform of a vector in time.Emily Belli
An algorithm that computes the discrete Fourier transform and its inverse with order n log n operations.Tristan Buckmaster
An efficient algorithm to compute the discrete Fourier transform of a sequence.
Lectures that assume it
1Connections
21The lectures that define it or assume it, and the concepts next to it.