(1) [5 points] Read polynomial multiplication as an application of FFT (Appendix-A.2, A.3). Take 2 polynomials of degree 3 each, and show how to multiply them. Show all the steps. For DFT and IDFT, feel free to use the recursive algorithm or multiplication by Vandermonde's matrix. Your sheet should show all calculations.

(2) [5 points, page limit 2 pages] Design a O(n, M poly(log M)) algorithm to count the number of distinct triplets from a set of n arbitrary positive integers, all in the range of 1 and M, that add to M/2 (assume M is even).
So, if X = {12,33,23,46,2,13} and M=54 then the answer is 1 triplet (12,2,13). Use FFT. Discuss its time complexity.

(3) [5 points, page limit 3 pages] Generalise (2) to design an FFT-based algorithm to identify if a set of arbitrary non-zero integers (contains positive and negative integers) has a distinct 5-tuple whose sum is 0. Discuss its time complexity. Assume that the numbers are between -M and M for some constant M.

By a distinct tuple I mean that it should have no repetition among its elements.

* (3) is difficult in the form that is given in the homework, so if you can only solve a special case or under certain assumptions, then go ahead and we will try to award partial marks. Your solution should use the FFT algorithm but you may relax the notions of distinctness. Here is one that is graded out of 3 (instead of 5): Design an FFT-based algorithm to identify if a set of arbitrary non-zero integers (contains positive and negative integers) has a 5-tuple whose sum is 0. Discuss its time complexity. Assume that the numbers are between -M and M for some constant M.