=================  Practice this before the tutorial ==============
0. Arrange several papers and pens/pencils.
0.5 Open wolframalpha.com for quick calculations of complex numbers.
1. Take any polynomial A(x) of degree 7. // Every student should ideally use your own polynomial to obtain maximum practice.
2. Compute the DFT (of order 8) of A(x). Call the values A=[A0 ... A7].
3. Write down the 8x8 Vandermonde's matrix V8.
4. Let the row vector a = [a0 ... a7] represent the coefficients of A(x).
5. Multiple V8 * transpose(a) to obtain a column vector.
5.5 Check that you are getting transpose(A) as the column vector after multiplication. Convince yourself that this is not a coincidence.
6. Write down the inverse of V8 - call it W8.
7. Multiple W8 * A. Check that you are getting the vector transpose(a).
8. Compute the values B0 ... B7 using the following formula.
Bk = (1/8) * \sum_j=0^7 Aj*w_8^{-jk}
9. Design an algorithm for IDFT -- an algorithm to compute B0...Bk using the Odd/Even recursive idea discussed in the lecture (what would be the polynomial?). You should see that computing the IDFT (inverse DFT) of A can be done by recursively evaluating the IDFTs of two polynomials, and combining them in the _exact_same_manner_as_we_did_for_DFT_.
10. Run your recursive algorithm from 9 on B(x).
10.5 Check that the vectors a and B=[B0 ... B7] are identical. Convince yourself that this is not a coincidence.

100. Now minutely go over each step of the DFT and the IDFT algorithm.
1000. Prepare yourself as if there would be a quiz on Lec5 during Thursday's lecture.

============== Tutorial ================

1. Exercise 1, Jeff-Appendix-FFT (Minkowski sum)

2. Solve T(n) = T(n/9) + T(4n/9) + O(n) using guessing and proving using induction by following the steps below.
(a) Draw the recursion tree for 3-4 levels.
(b) What can you say about the number of leaves? Can you upper bound it? Can you lower bound it? Suppose the number of leaves is Theta(L(n)). Then, the total work done in all base cases is O(L_1(n)) and Omega(L_2(n)).
(b) What is the work done in the 1st level? In the second level? In the k-th level? What can you say about the total work done in all the levels if the work done in each level decreases geometrically? If you cannot give a tight answer (because the tree is not a perfect binary tree), can you upper bound it? Can you lower bound it? Suppose the total work done in all the level is O(H_1(n)) and Omega(H_2(n)).
(c) Compute the upper and lower bounds: T(n) = Omega(L_2(n) + H_2(n)) and T(n) = O(L_1(n) + H_1(n)).

3. Solve (2) and then try to solve T(n,n)=O(____) for the recurrence T(n,m) = T(n,m/2) + T(n-m/2,m/2) + c n m log(n) log(m), where c is some positive constant, with the base case T(n,1)=c. Use the method for Q2. Use clever upper and lower bounds to simplify expressions.

4.* Try Problem 6 from Jeff-Appendix-FFT if you are bored.