## 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.