Description
1 Question 1
Note that in the last problem we used bucket sort in for n buckets in O(n) time. For this problem
we do almost the same thing except that we define integer a = d
1
e
e and we sort the n numbers into
a × n buckets. Thus, the algorithm is:
1. Sort the n numbers into a × n buckets – O(n).
2. For each bucket, find the minimum and maximum number – O(n).
3. Output the permutation by going through each bucket in order whilst making sure the minimum number for each bucket is the first number in that bucket and the maximum number
is the last.
Explanation:
This will ensure that the required condition (Σn
i=2|yi−yi−1| < 1+e) is met due to the following logic:
The maximum difference between any 2 elements in the same bucket is the size of that bucket
which is 1
an
.
Thus the maximum sum of differences that can be accrued by numbers in the one bucket (in
any order) is: 1
an × k ≤
k
an where k represents the total number of numbers in the bucket.
The sum of all the differences between numbers that are in the same bucket is thus: Σ ki
an ≤
Σki
an =
n
an =
1
a < e
Then we must also add the maximum sum accrued from bucket to bucket throughout the entire array. Since the bins are in order, and the minimum of each bucket must be the first for that
bucket and the maximum of each bucket must be the last of that bucket it is clear that this is less
than or equal to 1.
Thus, the total sum of difference between each number in order is: Σn
i=2|yi − yi−1| < 1 + e as
required.
Pseudocode:
xi → (xi
, bxianc) #Sort into buckets 0 .. an – 1
declare permutation as list
for each bucket 0 .. an – 1:
1
append minimum of bucket to permutation
append remaining values except for maximum to permutation
append maximum of bucket to permutation
2 Question 2
By writing out the bits of the i
th element in the original sequence and the i
th element in the
resulting permutation I found that element i in the permutation can be found by reversing the bits
of element i in the original sequence.
Consider the example given:
(0, 1, 2, 3, 4, 5, 6, 7) − > (0, 4, 2, 6, 1, 5, 3, 7)
Now lets write the original sequence in binary:
(000, 001, 010, 011, 100, 101, 110, 111)
If we then reverse the bits in each element we obtain:
(000, 100, 010, 110, 001, 101, 011, 111) = (0, 4, 2, 6, 1, 1, 3, 7)
which is the resulting permutation.
That is the resulting permutation is found by writing the original sequence in binary and reversing the bits of each element.
This sequence can be described by the recursive formula:
Pn = {2 · Pn−1, 1 † 2 · Pn−1}
W here, P1 = {0}
Where:
• a · P is the sequence created by multiplying every element in P by a e.g. 4 · {3, 6, 1, 9, 0} =
{6, 12, 2, 18, 0}.
• a † P is the sequence created by adding a to every element in P e.g. 5 · {2, 3, 1, 1, 7} =
{3, 4, 2, 2, 8}.
• {P1, P2} is the sequence created by appending P2 to the end of P1 e.g. {{3, 2, 6}, {7, 8, 7}} =
{3, 2, 6, 7, 8, 7}.
2
To show how this works lets produce the sequence for n = 5 i.e. P5:
P5 = {2 · P4, 1 † 2 · P4}
Now, P4 = {2 · P3, 1 † 2 · P3}
Now, P3 = {2 · P2, 1 † 2 · P2}
Now, P2 = {2 · P1, 1 † 2 · P1}
= {2 · {0}, 1 † 2 · {0}}
= {{0}, 1 † {0}}
= {0, 1}
T herefore, P3 becomes :
P3 = {2 · {0, 1}, 1 † 2 · {0, 1}}
= {{0, 2}, 1 † {0, 2}}
= {0, 2, 1, 3}
T herefore, P4 becomes :
P4 = {2 · {0, 2, 1, 3}, 1 † 2 · {0, 2, 1, 3}}
= {{0, 4, 2, 6}, 1 † {0, 4, 2, 6}}
= {{0, 4, 2, 6, 1, 5, 3, 7}}
T herefore, P5 becomes :
P5 = {2 · {0, 4, 2, 6, 1, 5, 3, 7}, 1 † 2 · {0, 4, 2, 6, 1, 5, 3, 7}}
= {{0, 8, 4, 12, 2, 10, 6, 14}, 1 † {0, 8, 4, 12, 2, 10, 6, 14}}
= {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
3 Question 3
This question is solved by recursion. For each node we first balance the left and right subtrees
which will inturn balance their left and right subtrees until we reach the leaf nodes at which point
the recursion will begin to unravel.
Note: In this context balance describes the act of increasing the edges in the tree in such a way
that ensures that the signal reaches the leafs in the same time from a given node.
The base case for this recursion involves a tree of depth 1 with a root node and left child and a
right child. To balance this base case we simply increase the lowest edge length until it equals the
higher edge length.
Pseudocode:
typedef struct Node{
Node *left;
Node *right;
int leftLength;
int rightLength;
}
3
void balanceBinTree(binTree t){
balance(t.root);
}
int balance (Node* n){
if(n->right->right == NULL){
if(n->leftLength < n->rightLength)
n->leftLength == n->rightLength;
else if(n->rightLength < n->leftLength)
n->rightLength = n->leftLength;
return n->rightLength;
}else
int left = balance(n->left) + n->leftLength;
int right = balance(n->right) + n->rightLength;
while(left < right){
n->leftLength++;
left++;
}while(right < left){
n->rightLength++;
right++;
}
return left;
}
}
Example walk through: Lets say we have the un-balanced binary tree as shown here:
Through the recursive algorithm the subtrees with nodes D, E, F, G will be balanced first by increasing the smaller edge length (leftLength or rightLength) to the larger edge length.
4
Then the recursion will unravel one step and the tree can be simplified as shown:
Thus we then balance the subtrees with root nodes B and C in the same fashion as above.
For example: Looking at node B. The leftLength is now 4+ 3 = 7 and the rightLength is 6+ 5 = 11
thus we need to add 11 − 7 = 4 to the leftLength which is done by adding 4 to the length B-D.
This is repeated for node C.
5
The recursion unravels again and the tree is simplified to the following:
Thus, we can repeat the process again for node A.
Now we have fully balanced the tree:
6
4 Question 4
The algorithm required for this question is simple:
1. Start at one end
2. Put first base station so the first house (H1) is just close enough to receive reception (i.e.
5km further down the road from H1).
3. Problem is now reduced to a road of length D − d with H − h houses. Where D is the total
length of the road, d is the length from the start of the road to the furthest reception provided
by the base station, H is the total number of houses on the road, h is the number of houses
who are provided with reception by the base station. D, d, H, h are further explained in
the figure below.
4. Check if any houses still require service. If so, repeat steps 2, 3, 4.
Further explanation:
Consider the following set of figures which demonstrate how the algorithm will work on a given
road. Note that the symbols have the following definitions:
• = a house on the road.
⊗ = location of a base station.
{ } = range of the base station.
` − a = start, section, end of road.
Consider a road of total length D with total Houses H:
7
Now we apply step 1 & 2 of the algorithm:
Thus, the problem can now be simplified to the following:
Note:
This is a greedy algorithm since the algorithm always chooses the location of the base station to
be the furthest along the road whilst still covering the first house that has not yet been covered.
5 Question 5
Basically I have solved this question using a greedy algorithm which involves selecting the most
valuable coin possible at each selection.
8
Algorithm:
Let amount be n and c be the collection of coins to pay with.
while(n > 0){
if(n >= 2)
add a $2 coin to c
n -= 2
else if(n >= 1)
add a $1 coin to c
n -= 1
else if(n >= 0.5)
add a 50c coin to c
n -= 0.5
else if(n >= 0.2)
add a 20c coin to c
n -= 0.2
else if(n >= 0.1)
add a 10c coin to c
n -= 0.1
else if(n >= 0.05)
add a 5c coin to c
n -= 0.05
}
Argue that it is optimal:
Since each coin is a multiple of smaller coins and the difference between each coin is
non-decreasing, we can show that $(n−c) can be paid with less coins than $n where c represents
the largest coin that is less than or equal to n: c ≤ n. Thus, the greedy solution above will produce
an optimal solution.
More formal proof:
Assume an optimal and greedy solutions for a price of p are given by
{o1, o2, o3, …, on}
{g1, g2, g3, …, gm}
respectively. Where the coins in the optimal solution are sorted from largest value (o1) to the
lowest value (on) since order for this problem does not matter. (Note that the greedy solution will
already be sorted in this manner).
Now, since the greedy solution always takes the highest value coin possible we can say that:
g1 ≥ o1
T hus, p − g1 ≤ p − o1
Thus, the greedy solution must now have the same or less money required to pay. This can be
recursed to show that the greedy solution is optimal.
9
6 Question 6
Since in the denominations 1, c, c2
, c3
, …, cn
each denomination is a multiple of smaller denominations (since c
k = c × c
k−1
) and the difference between the denominations is non-decreasing, this
question can be argued with the same logic as question 5. As such the greedy algorithm is
optimal.
7 Question 7
A set of denominations containing the single cent coin for which the greedy algorithm does not
always produce an optimal solution is 1c, 6c, 7c, 8c.
Take for example an amount of 13c:
The greedy algorithm would produce 8c, 1c, 1c, 1c, 1c, 1c whilst the optimal solution is 7c, 6c.
8 Question 8
TODO
9 Question 9
Greedy solution:
1. Starting from the left pick the first black dot. Connect this dot to the white dot that is closest
to the start.
2. Pick the next left-most black dot and connect it to the left-most white dot that is available
(i.e. not already connected to a black dot).
3. Repeat 2 until all black dots are connected to a corresponding white dot.
For example, my greedy algorithm would produce the following given the example case:
Logically, it is optimal due to the following argument: Say we don’t connect the left-most black
dot with the left-most white dot and we go further along the line by s spaces. Then we have already
worsened the greedy solution by length s. We can never get back more than these s spaces (however
it is very possible to get back exactly these s-spaces in which case the solution is optimal but not
greedy).
10
10 Question 10
Let A(x) be the polynomial of degree 16 and B(x) be the polynomial of degree 8. i.e.
A(x) = a0 + a1x + a2x
2 + a3x
3 + … + a16x
16
B(x) = b0 + b1x + b2x
2 + b3x
3 + … + b8x
8
Note that if we were to multiply this polynomial out in the current forms it would require 17 × 9 =
153 multiplications.
The algorithm to multiply these two polynomials using only 25 multiplications is:
1. Pad A(x) with degree of B 0’s. i.e. with 8 0’s and pad B(x) with degree of A 0’s. i.e. with
16 0’s:
A(x) = a0 + a1x + a2x
2 + a3x
3 + … + a16x
16 + 0x
17 + 0x
18 + … + 0x
24
B(x) = b0 + b1x + b2x
2 + b3x
3 + … + b8x
8 + 0x
9 + 0x
10 + … + 0x
24
2. Use FFT to obtain the value representation of the padded A(x) and the padded B(x). i.e.:
A(x)
F F T ===⇒ {A(1), A(ω25), A(ω
2
25), A(ω
3
25), …, A(ω
24
25)}
B(x)
F F T ===⇒ {B(1), B(ω25), B(ω
2
25), B(ω
3
25), …, B(ω
24
25)}
Note that process for FFT is described in the appendix below.
3. Obtain the value representation of the polynomial C (C(x) = A(x) · B(x)) by multiplication
of each term in the above value representations. i.e.:
C(x) (in value representation) = {A(1)B(1),A(ω25)B(ω25), A(ω
2
25)B(ω
2
25),
A(ω
3
25)B(ω
3
25), …, A(ω
24
25)B(ω
24
25)}
Note that this step requires precisely 25 multiplications.
4. Use IFFT to obtain the polynomial form of C(x). i.e.:
{A(1)B(1),A(ω25)B(ω25), A(ω
2
25)B(ω
2
25),
A(ω
3
25)B(ω
3
25), …, A(ω
24
25)B(ω
24
25)}
IF F T ====⇒ C(x)
Note that process for IFFT is described in the appendix below.
11
11 Question 11
ω
k
n = (ωdn)
dk
∴ i(ω64)
7
(ω32)
15 = i(ω64)
7
(ωd×32)
d×15
= i(ω64)
7
(ω2×32)
2×15 (d = 2)
= i(ω64)
7
(ω64)
30
= i(ω64)
7+30
= i(ω64)
37
= (ω64)
37+ 64
4 (since multiplication
by i is an anticlockwise
rotation of 90 deg)
= (ω64)
53
= ω
53
64
12 Question 12
12.1 12a
Note that if we were to multiply this polynomial out in the current forms it would require 4×4 = 16
multiplications.
The algorithm to multiply these two polynomials using only 7 multiplications is:
1. Let y = x
2 and solve for
P(y) = a0 + a2y + a4y
2 + a6y
3 andQ(y) = b0 + b2y + b4y
2 + b6y
3
2. Pad P(y) with degree of Q 0’s. i.e. with 3 0’s and pad Q(x) with degree of A 0’s. i.e. with 3 0’s:
P(y) = a0 + a2y + a4y
2 + a6y
3 + 0y
4 + 0y
5 + 0y
6
Q(y) = b0 + b2y + b4y
2 + b6y
3 + 0y
4 + 0y
5 + 0y
6
3. Use FFT to obtain the value representation of the padded P(y) and the padded Q(y). i.e.:
P(y)
F F T ===⇒ {P(1), P(ω7), P(ω
2
7
), P(ω
3
7
), …, P(ω
6
7
)}
Q(y)
F F T ===⇒ {Q(1), Q(ω7), Q(ω
2
7
), Q(ω
3
7
), …, Q(ω
6
7
)}
Note that process for FFT is described in the appendix below.
4. Obtain the value representation of the polynomial C (C(y) = P(y) · Q(y)) by multiplication
of each term in the above value representations. i.e.:
12
C(y) (in value representation) = {P(1)Q(1),P(ω7)Q(ω7), P(ω
2
7
)Q(ω
2
7
),
P(ω
3
7
)Q(ω
3
7
), …, P(ω
6
7
)Q(ω
6
7
)}
Note that this step requires precisely 7 multiplications.
5. Use IFFT to obtain the polynomial form of C(y). i.e.:
{P(1)Q(1),P(ω7)Q(ω7), P(ω
2
7
)Q(ω
2
7
),
P(ω
3
7
)Q(ω
3
7
), …, P(ω
6
7
)Q(ω
6
7
)}
IF F T ====⇒ C(y)
Note that process for IFFT is described in the appendix below.
6. Now find C(x) by replacing everyone value of y in C(y) with x
2
12.2 12b
Note that if we were to multiply this polynomial out in the current forms it would require 5×5 = 25
multiplications.
The algorithm to multiply these two polynomials using only 16 multiplications is:
1. Write the polynomials like so:
P(x) = a0 + x
17(a17 + a19x
2 + a21x
4 + a23x
6
)
Q(x) = b0 + x
17(b17 + b19x
2 + b21x
4 + b23x
6
)
Therefore, we can multiply the two as such:
P(x)Q(x) = (a0 + x
17(a17 + a19x
2 + a21x
4 + a23x
6
)) × (b0 + x
17(b17 + b19x
2 + b21x
4 + b23x
6
))
= a0b0 + a0x
17(b17 + b19x
2 + b21x
4 + b23x
6
) + b0x
17(a17 + a19x
2 + a21x
4 + a23x
6
)
+ x
17x
17(a17 + a19x
2 + a21x
4 + a23x
6
)(b17 + b19x
2 + b21x
4 + b23x
6
)
= a0b0 + a0b17x
17 + a0b19x
19 + a0b21x
21 + a0b23x
23 + b0a17x
17 + b0a19x
19 + b0a21x
21
+ b0a23x
23 + x
34(a17 + a19x
2 + a21x
4 + a23x
6
)(b17 + b19x
2 + b21x
4 + b23x
6
)
Now, if we let
(a17 + a19x
2 + a21x
4 + a23x
6
) = A(x)(b17 + b19x
2 + b21x
4 + b23x
6
) = B(x)
13
Then the last line of the above equation becomes (here I will explicitly put a × for each
multiplication of coefficients):
P(x)Q(x) = a0 × b0 + a0 × b17x
17 + a0 × b19x
19 + a0 × b21x
21 + a0 × b23x
23 + b0 × a17x
17
+ b0 × a19x
19 + b0 × a21x
21 + b0 × a23x
23 + x
34A(x)B(x)
Thus, we have 9 multiplications + the multiplications required for A(x)B(x).
It is very important to note that A(x) and B(x) are the exact same form as the equations
P(x) and Q(x) in (12a). In 12a we showed that these two equations can me multiplied together with only 7 multiplications, I will not repeat the work here.
Thus, #multiplications = 9 + 7 = 16 as required.
12.3 12c
Note that if we were to multiply this polynomial out in the current forms it would require 2 ×2 = 4
multiplications.
The algorithm to multiply these two polynomials using only 7 multiplications is:
1. Let y = x
100 and solve for
P(y) = a0 + a100y andQ(y) = b0 + b100y
2. Pad P(y) with degree of Q 0’s. i.e. with 1 0 and pad Q(x) with degree of A 0’s. i.e. with 1 0:
P(y) = a0 + a100y + 0y
2
Q(y) = b0 + b100y + 0y
2
3. Use FFT to obtain the value representation of the padded P(y) and the padded Q(y). i.e.:
P(y)
F F T ===⇒ {P(1), P(ω3), P(ω
2
3
)}
Q(y)
F F T ===⇒ {Q(1), Q(ω3), Q(ω
2
3
)}
Note that process for FFT is described in the appendix below.
4. Obtain the value representation of the polynomial C (C(y) = P(y) · Q(y)) by multiplication
of each term in the above value representations. i.e.:
C(y) (in value representation) = {P(1)Q(1),P(ω3)Q(ω3), P(ω
2
3
)Q(ω
2
3
)}
Note that this step requires precisely 3 multiplications.
14
5. Use IFFT to obtain the polynomial form of C(y). i.e.:
{P(1)Q(1),P(ω3)Q(ω3), P(ω
2
3
)Q(ω
2
3
)}
IF F T ====⇒ C(y)
Note that process for IFFT is described in the appendix below.
6. Now find C(x) by replacing every value of y in C(y) with x
100
13 Appendix
13.1 FFT
Fast Fourier Transform is a process that carries out a discrete Fourier transform on a polynomial.
That is, it takes the coefficient form of a polynomial and produces the value form of that polynomial. I have used it several times in the above assignment and thus will describe the algorithm here.
Algorithm (taken from lecture notes):
F F T(A)
n ← length[A]
if n = 1
return A
A
[0] ← (A0, A2, …, An−2)
A
[1] ← (A1, A3, …, An−1)
y
[0] ← F F T(A
[0])
y
[1] ← F F T(A
[1])
ωn ← e
2π
n
ω ← 1
for k = 0 to k = n/2 − 1 do :
yk ← y
[0]
k + ω · y
[1]
k
yk+n/2 ← y
[0]
k − ω · y
[1]
k
ω ← ω · ωn
return y
Another way to look at it is:
A(x) = A0 + A1x + A2x
2 + … + An−1x
n−1 F F T ===⇒ {A(1), A(ωn), A(ω
2
n
), …, A(ω
n−1
n
)}
This process can be carried out by using the FFT matrix:
15
With the following equation:
13.2 IFFT
Inverse Fast Fourier Transform is the inverse of the above process. That is, it takes the value
representation of a polynomial and provides the coefficient form of a polynomial. This can be done
using the same algorithm as shown for FFT but changing all ω
i
toω−1
.
In the matrix form, the equation is the same as for FFT except we use the inverse of the matrix:
However,
16 Thus,
17
