In this problem you will use the fast fourier transform on


(A) Split into its even and odd components:



(B) Compute the Fourier transforms of the even and odd components:



(C) Combine the Fourier transforms of the even and odd components to get the transform of









You can earn partial credit on this problem.