Description
1) Improve the result from problem 5 of the previous assignment by showing that for every e> 0, 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 n numbers, say y1, …., yn, such that
n
i=2 |yi – yi-1| < 1 + e.
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) 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
n
-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
th element of the original
sequence and the i
th 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 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
15.)
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 range of Telstra’s cell base station is 5km. Design an algorithm for placing
the minimal number of base stations alongside the road, that is sufficient to cover all houses.
5) Assume you have $2, $1, 50c, 20c, 10c and 5c coins to pay for your lunch. Design an algorithm that, given
the amount that is a multiple of 5c, pays it with a minimal number of coins and argue that it is optimal.
6) Assume denominations of your coins are 1, c, c2
, c
3
, …, c
n
for some integer c > 1. Is the greedy algorithm,
which, given any amount, pays it with the largest possible denominations first, optimal i.e. resulting in a
minimal number of coins?
7) Give an example of a set of denominations containing the single cent coin for which the greedy algorithm
does not always produce an optimal solution.
8) Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has
made up a list of which pairs of these people know each other. She wants to pick as many people as
possible, subject to two constraints: at the party, each person should have at least five other people whom
they know and at least five other people whom they do not know. Give an efficient algorithm that takes as
input the list of n people and the list of all pairs who know each other and outputs a subset of these n people
which satisfies the constraints and which has the largest number of invitees. Argue that your algorithm
indeed produces a subset with the largest possible number of invitees.
9) Assume that you are given n white and n black dots, lying on a line, equally spaced. The dots appear in any
order of black and white, see the example picture below. Design a greedy algorithm which connects each
black dot with a (different) white dot, so that the total length of wires used to form such connected pairs is
minimal. The length of wire used to connect two dots is equal to their distance along the line.
15
1 2
2 1 1 3
3 2
2 2 3 3
1 2
4 4 3 3
A C
B
10) Design an algorithm which multiplies any polynomial of degree 16 with any polynomial of degree 8 using
only 25 multiplications in which both operands can be arbitrarily large.
11) Simplify the expression i (ω64)
7
(ω32)
15 where i is the imaginary unit.
12) Multiply the following three pairs of polynomials using at most the prescribed number of multiplications of
large numbers (large numbers are those which depend on the coefficients thus can be arbitrarily large).
(a) P(x) = a0 + a2 x
2 + a4 x
4 + a6 x
6
; Q(x) = b0 + b2 x
2 + b4 x
4 + b6 x
6
using at most 7 multiplications of
large numbers;
(b) P(x) = a0 + a17 x
17 + a19 x
19 + a21 x
21+ a23 x
23
; Q(x) = b0 + b17 x
17 + b19 x
19 + b21 x
21+ b23 x
23 using at
most 16 multiplications of large numbers;
(c) P(x) = a0 + a100 x
100 and Q(x) = b0 + b100 x
100
with at most 3 multiplications of large numbers.
