CSCI5454 Homework 3- Divide-And-Conquer Algorithms and Fast-Fourier Transform Solution

P1.  In class, we showed a divide and conquer algorithm for Fast Fourier Transforms (FFT) wherein given a sequence ⟨a0,...,an−1⟩, we divided into two subsequences of length n/2 to wit: a0,a2,...,an−2 and a1,a3,...,an−1. Assume n is some power of two.
In this problem, we ask you to consider dividing the sequence of n numbers into two subsequences: and .
Part A (2 points) Let polynomial and consider polynomials and . Express p(x) in terms of p1 and p2.
Part B (10 points) Consider the sequence ⟨b0,...,bn/2−1⟩ wherein b0 = a0 + an/2,b1 = a1 + an/2+1,··· ,bj = aj + an/2+j,··· ,bn/2−1 = an/2−1 + an−1 .
Let be the FFT for that sequence. Show that A2k = Bk for any k = 0,...,n/2−1.
Part C (10 points) Consider the sequence ⟨c0,c1,...,cn/2−1⟩ wherein ck = (ak − ak+n/2) × ωnk. Let ⟨C0,...,Cn/2−1⟩ be its Fourier coefficients. Show that A2k+1 = Ck.
Part D (8 points) Propose an alternative divide and conquer scheme for computing FFT by putting together the two observations from the previous two parts. Write the pseudo-code and derive the complexity. In the pseudo code there is no need to write down the code for base case: just add a comment to the effect that the “base case code goes here” or assume there is a function naive-dft that would compute DFT coefficients in O(n2) time.
P2 (20 points) We have a directory in a computer with n files where n is a large even number. These files are numbered from 1 to n. Design an efficient algorithm to check if a majority of the files are identical and if so which file it is.
• If n is even then majority means at least one more than n/2. If n is odd, majority is simply ⌈n/2⌉.
• You can check if two files are the same (presumably by rapid bitwise comparison).
• You cannot sort the files based on their contents since there is no ≤ comparison between files.
• No hashing, bitwise operations or arithmetic operations over file contents allowed.
Part A (10 points) Design a divide and conquer algorithm for this problem that runs in O(nlogn) time. Justify the time complexity briefly.
Part B (10 points) Design an even more efficient divide and conquer algorithm that runs in O(n) time. Justify why it runs in O(n) time.
Hint: Pair up the first file with the second, third with the fourth and so on. Test for each of the pair of files if they are the same. If not, discard both files in the pair. If yes, keep just one of the files in the pair. If there was a majority of identical files, what can you say about the remaining files? If there was no majority, then what? Rinse and repeat the process. Think of modifications if n were an odd number?
1
P3 (10 points) In class, we demonstrated the algorithm to find the closest pair of points on a plane. We obtained the recurrence
T(n) = 2T(n/2) + O(nlog(n)),
and a suitable base case. In the previous assignment, we proved that this leads to a overall time complexity of O(n(log(n)2)).
Explain how you would modify the algorithm to compute the closest pair of points in O(nlog(n)) time. Recall the outline of the algorithm:
• Sort the points using their x coordinates. • Recursively carry out the following steps:
– If number of points is less than 10 just do pairwise comparisons.
– Otherwise, split the list into two lists of size n/2 along the median x coordinate.
– Recursively compute the closest pair for both halves.
– Take the minimum of the two distances obtained from the two calls.
– Sort the points in the “central strip” along the y coordinate.
– Iterate through the list and compare each point in the sorted list from previous step to the eight previous points.
(i) Explain which steps contribute to the n(log(n))2 complexity; (ii) explain how that step can be made faster to obtain nlog(n) complexity.
2