30.2 The DFT and FFT

30.2-1

Prove Corollary 30.4.

(Omit!)

30.2-2

Compute the $\text{DFT}$ of the vector $(0, 1, 2, 3)$.

(Omit!)

30.2-3

Do Exercise 30.1-1 by using the $\Theta(n\lg n)$-time scheme.

(Omit!)

30.2-4

Write pseudocode to compute $\text{DFT}_n^{-1}$ in $\Theta(n\lg n)$ time.

(Omit!)

30.2-5

Describe the generalization of the $\text{FFT}$ procedure to the case in which $n$ is a power of $3$. Give a recurrence for the running time, and solve the recurrence.

(Omit!)

30.2-6 $\star$

Suppose that instead of performing an $n$-element $\text{FFT}$ over the field of complex numbers (where $n$ is even), we use the ring $\mathbb Z_m$ of integers modulo $m$, where $m = 2^{tn / 2} + 1$ and $t$ is an arbitrary positive integer. Use $\omega = 2^t$ instead of $\omega_n$ as a principal nth root of unity, modulo $m$. Prove that the $\text{DFT}$ and the inverse $\text{DFT}$ are well defined in this system.

(Omit!)

30.2-7

Given a list of values $z_0, z_1, \dots, z_{n - 1}$ (possibly with repetitions), show how to find the coefficients of a polynomial $P(x)$ of degree-bound $n + 1$ that has zeros only at $z_0, z_1, \dots, z_{n - 1}$ (possibly with repetitions). Your procedure should run in time $O(n\lg^2 n)$. ($\textit{Hint:}$ The polynomial $P(x)$ has a zero at $z_j$ if and only if $P(x)$ is a multiple of $(x - z_j)$.)

(Omit!)

30.2-8 $\star$

The chirp transform of a vector $a = (a_0, a_1, \dots, a_{n - 1})$ is the vector $y = (y_0, y_1, \dots, y_{n - 1})$, where $y_k = \sum_{j = 0}^{n - 1} a_jz^{kj}$ and $z$ is any complex number. The $\text{DFT}$ is therefore a special case of the chirp transform, obtained by taking $z = \omega_n$. Show how to evaluate the chirp transform in time $O(n\lg n)$ for any complex number $z$. ($\textit{Hint:}$ Use the equation

$$y_k = z^{k^2 / 2} \sum_{j = 0}^{n - 1} \Big(a_jz^{j^2 / 2}\Big) \Big(z^{-(k - j)^2 / 2}\Big)$$

to view the chirp transform as a convolution.)

(Omit!)