Description
Problem 1 (Median algorithm)
Let A be an array of n distinct numbers. Let k < n/2. Design an algorithm that outputs the k
th
elements of A that are closest to the median of A. More precisely, your algorithm should return the
order statistics
{n/2 − k/2; n/2 − k/2 + 1; . . . , n/2 + k/2; n/2 + k/2}.
You can asume that both n and k are even.
Example: for A = [2, 5, 4, 9, 0, −1] and k = 2 your output should be the set {2, 4, 0}. In particular,
your output does not have to be sorted.
Use the algorithms discussed in class as black-boxes. Do not use pseudocode. Explain why your
algorithm is correct and analyze its running time. Faster and correct solutions are worth more credit.
Problem 2 (Integer multiplication using FFT)
(a) Given an n−bit integer number a = a0a1a2 . . . an−1 define a polynomial A(x) satisfying A(2) =
a.
(b) Given two n−bit integers a and b, give an algorithm to multiply them in O(n log(n)) time.
Use the FFT algorithm from class as a black-box (i.e. don’t rewrite the code, just say run
FFT on …).Explain your algorithm in words and analyse its running time.