Problem 2. (a) (10 points) Suppose that you are given a polynomial n-1 k=0 The input to the FFT of length n is given by an array containing the coefficients (ao,...,an-1). Describe the output of the FFT in terms of the polynomial A(). (b) (10 points) Let be a primitive nth root of unity. The fast Fourier trans- form implements the multiplication with the matrix F= (wij)i,j in(..n-1]. Can someone give me all the answer is given please!!! Show that the inverse of the F is given by [Hint: z"-1 = (z-1 )(z"-i + . . . +z + 1), so any power w,41 must be a root of -1 +. . . +z+1. ] Thus, the inverse FFT, called IFFIE, is nothing but the FFT using -1 instead of w, ald multiplying the result with 1. (c) (10 points) Describe how to do a polynomial multiplication using the FFT (d) (15 points) How can you modify the polynomial multiplication algorithm (e) (5 points) What kind of problems can occur in the previous approach to and IFFT for polynomials A(z) and B(z) of degree S n 1. Make sure that you describe the length of the FFT and IFFT needed for this task. based on FFT and IFFT to do multiplication of long integers in base 10? Make sure that you take care of carries in a proper way multiply long integers and how would you overcome them? Hint: How does the idealized FFT algorithm differ from a version implemented on a computer