To evaluate FFT(a0,a1,a2,a3,a4,a5,a6,a7) we apply recursively FFT and obtain
FFT( a0,a2,a4,a6) and FFT(a1,a3,a5,a7). Proceeding further with recursion, we obtain FFT(a0,a4) and
FFT(a2,a6) as well as FFT(a1,a5) and FFT(a3,a7). Thus, from bottom up, FFT(a0,a1,a2,a3,a4,a5,a6,a7) is
obtained using permutation (a0,a4,a2,a6,a1,a5,a7) as the leaves of the recursion tree of the original input
sequence. Given any input (a0,a1,a2,…a2
-1) describe the permutation of the leaves of the recursion tree.
(Hint: write indices in binary and see what the relationship is of the bits of the i
element of the original
sequence and the i
element of the resulting permutation of elements as they appear on the leaves on the
3) Timing Problem in VLSI chips. Consider a complete balanced binary tree with
n = 2k
leaves. Each edge has an associate positive number that we call the length of this edge (see picture
below). The distance from the root to a leaf is the sum of the lengths of all edges from the root to this leaf.
The root sends a clock signal and the signal propagates along the edges and reaches the leaf in time
proportional to the distance from the root to this leaf. Design an algorithm which increases the lengths of some of the edges in the tree in a way that ensures that the signal reaches all the leafs in the same time
while the sum of the lengths of all edges is minimal. (For example, on the picture below if the tree A is
transformed into trees B and C all leaves of B and C are on the distance 5 from the root and thus receive the
clock signal in the same time, but the sum of lengths of edges in C is 17 while sum of lengths in B is only
4) Along the long, straight road from Loololong to Goolagong houses are scattered quite sparsely, sometimes
with long gaps between two consecutive houses. Telstra must provide mobile phone service to people that
live alongside the road, and the...