Description

Some hints and tips:
• Read the assignment early, so you have time to think about the problems!
• Read all the problems and make sure you understand them: sometimes problems can be difficult to understand, but easy once understood.
• Concise answers written in clear English text are perfectly acceptable, as are answers written in clear pseudocode.
Hint: Remember that FFT does not multiply polynomials, what does it do? Refer to the lecture slides.
(b) In this part we will extend the Fast Fourier Transform (FFT) algorithm described in class to multiply multiple polynomials together (not just two).
Suppose you have K polynomials P1,…,PK so that
degree(P1) + ··· + degree(PK) = S
(i) [5 marks] Show that you can find the product of these K polynomials in O(KS logS) time.
Hint: How many points do you need to uniquely determine an Sdegree polynomial?
(ii) [10 marks] Show that you can find the product of these K polynomials in O(S logS logK) time. Explain why your algorithm has the required time complexity.
Hint: consider using divide-and-conquer!
For example, if there are N = 3 coins in the bag with values 1, 4 and 5 (so we could have M = 5), then the possible sums are 5, 6 and 9.
Hint: if the coins have values v1,…,vN, how might you use the polynomial xv1 + ··· + xvN?
3. Let us define the Fibonacci numbers as F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2 for all n ≥ 2. Thus, the Fibonacci sequence looks as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
(a) [5 marks] Show, by induction or otherwise, that

for all integers n ≥ 1.
Hint: Suppose N = A + B and pretend you wish to sell all items to Alice, but must choose B of them to give to Bob instead. Which ones do you want to give to Bob first? Then extend your approach to handle N < A + B as well.
5. Your army consists of a line of N giants, each with a certain height. You must designate precisely L ≤ N of them to be leaders. Leaders must be spaced out across the line; specifically, every pair of leaders must have at least K ≥ 0 giants standing in between them. Given N,L,K and the heights H[1..N] of the giants in the order that they stand in the line as input, find the maximum height of the shortest leader among all valid choices of L leaders. We call this the optimisation version of the problem.
For instance, suppose N = 10,L = 3,K = 2 and H = [1,10,4,2,3,7,12,8,7,2]. Then among the 10 giants, you must choose 3 leaders so that each pair of leaders has at least 2 giants standing in between them. The best choice of leaders has heights 10, 7 and 7, with the shortest leader having height 7. This is the best possible for this case.
(a) [10 marks] In the decision version of this problem, we are given an additional integer T as input. Our task is to decide if there exists some valid choice of leaders satisfying the constraints whose shortest leader has height no less than T.
Give an algorithm that solves the decision version of this problem in O(N) time.
(b) [10 marks] Hence, show that you can solve the optimisation version of this problem in O(N logN) time.