Mat 540 Week 1 Assignment

1004 Words5 Pages
Assignment #2 1) Improve the result from problem 4 of the previous assignment by showing that for every e> 0, no matter how small, given n real numbers x1,...,xn where each xi is a real number in the interval [0, 1], there exists an algorithm that runs in linear time and that will output a permutation of the numbers, say y1, ...., yn, such that ∑ ni=2 |yi - yi-1| < 1 + e. (Hint: use buckets of size smaller than 1/n; you might also need the solution to problem 3 from the first assignment!) 2) 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)…show more content…
Given any input (a0,a1,a2,…a2n-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 ith element of the original sequence and the ith element of the resulting permutation of elements as they appear on the leaves on the recursion tree.) 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…show more content…
The organizers of the party want it to be a fun party, and so have assigned a ‘fun’ rating to every employee. The employees are organized into a strict hierarchy, i.e. a tree rooted at the president. There is one restriction, though, on the guest list to the party: an employee and their immediate supervisor (parent in the tree) cannot both attend the party (because that would be no fun at all). Give an algorithm that makes a guest list for the party that maximizes the sum of the ‘fun’ ratings of the guests. 6) Cutting Sticks You have to cut a wood stick into several pieces. The most affordable company, Analog Cutting Machinery (ACM), charges money according to the length of the stick being cut. Their cutting saw allows them to make only one cut at a time. It is easy to see that different cutting orders can lead to different prices. For example, consider a stick of length 10 m that has to be cut at 2, 4, and 7 m from one end. There are several choices. One can cut first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 m, the resulting stick of 8 m, and the last one of 6 m. Another choice could cut at 4, then at 2, then at This would lead to a price of 10 + 4 + 6 = 20, which is better for us. Your boss demands that you design an algorithm to find the minimum possible cutting cost for any given stick. 7) Interleaving of Strings For bit strings X = x1 ... xm

More about Mat 540 Week 1 Assignment

Open Document