Tutorial 2 – Solutions
COMP3121/9101
Problems 1 to 10 are designated as [A], meaning that their solutions are written to the standard we expect in an assignment submission. You may wish to use at least these solutions as a guide for your own submissions.
1. [A] Determine the asymptotic growth rate of the solutions to the following recurrences. You may use the Master Theorem if it is applicable.
Copyright By PowCoder代写 加微信 powcoder
(a) T(n)=2T(n/2)+n(2+sinn) (b) T(n)=2T(n/2)+√n+logn
(c) T(n) = 8T(n/2) + nlog2 n (d) T(n)=T(n−1)+n
(a) Here, a = 2 and b = 2 so the critical exponent is c∗ =log22=1.
On the other hand,
f (n) = n(2 + sin n) = Θ(n)
because 1 ≤ 2 + sin n ≤ 3. Thus, the second case of the Master Theorem
applies and we get
(b) Again, the critical exponent is 1. On the other hand, we have
T (n) = Θ(n log n). √√
f(n)= n+logn=Θ( n). f(n) = O(n0.9) = O(nc∗−0.1)
This implies that
so the first case of the Master Theorem applies and we obtain
T (n) = Θ(n). 1
(c) Here, a = 8 and b = 2 so the critical exponent is c∗ =log28=3.
On the other hand, log2 n ≥ 4 for large n, so
In our case, this translates to
Now, we have
f(n) = nlog2 n = Ω(n4). f(n) = Ω(nc∗+1).
Consequently,
To be able to use the third case of the Master Theorem, we have to show
that for some 0 < c < 1 the following holds for sufficiently large n: af n < cf(n).
8nlog2 n2
so the required inequality is satisfied with c = 12 for all n > 16. Therefore by case 3 of the Master Theorem, the solution is
T(n) = Θ(f(n)) = Θ(nlog2 n). 2
(d) Note that for every k we have T(k) = T(k−1)+k. So we just unwind the recurrence to get
T (n) = T (n − 1) + n
= T (n − 2) + (n − 1) + n
= T (n − 3) + (n − 2) + (n − 1) + n
= T (1) + (n − (n − 2)) + (n − (n − 3)) + . . . + (n − 1) + n = T (1) + (2 + 3 + 4 + . . . + n)
= T(1)+ n(n+1) −1 2
2. [A] You are given a 2n × 2n board with one of its cells missing (i.e., the board has a hole). The position of the missing cell can be arbitrary. You are also given a supply of “trominoes”, each of which can cover three cells as below.
Your task is to design an algorithm which covers the entire board (except for the hole) with these “trominoes”. Note that the trominoes can be rotated.
Solution: We proceed by a divide and conquer recursion; thus, we split the board into 4 equal parts:
We can now apply our recursive procedure to the top left board which has a missing square. To be able to apply recursion to the remaining 3 squares we place a domino at the centre as shown below.
We treat the covered squares in each of the three pieces as a missing square and can proceed by recursion applied on all 4 squares whose sides are half the size of the size of the original square.
3. [A] You and a friend find yourselves on a TV game show! The game works as follows. There is a hidden N ×N table A. Each cell A[i, j] of the table contains a single integer and no two cells contain the same value. At any point in time, you may ask the value of a single cell to be revealed. To win the big prize, you need to find the N cells each containing the maximum value in its row. Formally, you need to produce an array M [1..N ] so that A[r, M [r]] contains the maximum value in row r of A, i.e., such that A[r,M[r]] is the largest integer among A[r, 1], A[r, 2], . . . , A[r, N ]. In addition, to win, you should ask at most 2N⌈logN⌉ many questions. For example, if the hidden grid looks like this:
Column 1 Column 2 Column 3 Column 4 Row1 10 5 8 3 Row2 1 9 7 6 Row3 -3 4 -1 0 Row4 -10 -9 -8 2
then the correct output would be M = [1, 2, 2, 4].
Your friend has just had a go, and sadly failed to win the prize because they asked N2 many questions which is too many. However, they whisper to you a hint: they found out that M is non-decreasing. Formally, they tell you that M[1] ≤ M[2] ≤ ··· ≤ M[N] (this is the case in the example above).
Design an algorithm which asks at most O(N log N) many questions that pro- duces the array M correctly, even in the very worst case.
Hint: Note that you do not have enough time to find out the value of every cell in the grid! Try determining M[N/2] first, and see if divide-and-conquer is of any assistance.
Solution: We first find M[N/2]. We can do this in N questions by simply examining each element in row N/2, and finding the largest one.
Suppose M[N/2] = x. Then, we know that M[i] ≤ x for all i < N/2 and that M[j] ≥ x for all j > N/2. Thus, we can recurse to solve the same problem on the sub-grids
N A1.. 2−1 [1..x]
A 2 +1 ..N [x..N].
It remains to show that this approach uses at most 2N⌈logN⌉ questions.
Claim: at each stage of recursion, at most two cells of any column are investi- gated.
• In the first call of the recursion, only one cell of each column has been investigated. These cells are marked in blue, with the maximum in dark blue.
• In the second call of the recursion, we investigate two cells of one column, and one cell of each of the other columns. These cells are marked in green, with the maxima in dark green.
• In the third call of the recursion, we investigate two cells in each of three columns, and one cell of each of the other columns. These cells are marked in orange.
Since the investigated ranges overlap only at endpoints, the claim holds true.
So in each recursion call, at most 2N cells were investigated. The search space decreases by at least half after each call, so there are at most ⌈log2 N⌉ many recursion calls. Therefore, the total number of cells investigated is at most 2N⌈log2 N⌉.
Additional exercise: using the above reasoning, try to find a sharper bound for the total number of cells investigated.
4. [A] Given positive integers M and n, compute Mn using only O(logn) many multiplications.
Solution: Note that
Mn= n−12
M n2 2 if n is even M2 ×M ifnisodd.
Hence, we can proceed by divide and conquer. If n is even, we recursively n n−1
compute M 2 and then square it. If n is odd, we recursively compute M 2 , square it and then multiply by another M. Since n is (approximately) halved in each recursive call, there are at most O(log n) recursive calls, and since we perform only one or two multiplications in each recursive call, the algorithm performs O(log n) many multiplications, as required.
Alternative Solution: Any positive integer n can be uniquely written in base 2, and therefore can be uniquely written as the sum of distinct powers of 2. Thus, Mn can be written the product of powers of M where the index is itself a power of 2, i.e. M,M2,M4,M8,…. We can obtain these powers of M in O(log n) time by repeated squaring, and then multiply together the appropriate powers to get Mn. The appropriate powers to multiply are the powers M2i such that the ith least significant bit of the binary representation of n is 1. For example, to obtain M11, the binary representation of 11 is 10112, and hence we should multiply together M, M2, and M8.
5. [A] Define the Fibonacci numbers as
F0 =0,F1 =1, andFn =Fn−1+Fn−2 foralln≥2.
Thus, the Fibonacci sequence is as follows: 0,1,1,2,3,5,8,13,21,….
(a) Show, by induction or otherwise, that
Fn+1 Fn 1 1n
for all integers n ≥ 1.
(b) Hence or otherwise, give an algorithm that finds Fn in O(log n) time.
Hint: You may wish to refer to Example 1.5 on page 28 of the “Review Mate- rial” booklet.
(a) Whenn=1wehave
FF=10 n n−1
Fn+1 Fn 1 1 FF=10
1 11 =10
so our claim is true for n = 1.
Let k ≥ 1 be an integer, and suppose our claim holds for n = k (Inductive
Hypothesis). Then
1 1k+1 1 1k 1 1
Fk+1 Fk 1 1 = −1 1 0
by the Inductive Hypothesis. Hence
1 1k+1 Fk+1 + +1
10 =Fk+Fk−1 Fk Fk+2 Fk+1
by the definition of the Fibonacci numbers. Hence, our claim is also true
for n = k + 1, so by induction it is true for all integers n ≥ 1. 7
1 1 G=10.
Now we can use either of the methods from the previous problem. i. We can use divide and conquer, recursively calculating
Gn2 2 if n is even n−12
G2 G ifnisodd.
At each of O(logn) steps of the recursion, we multiply either two or three 2-by-2 matrices in constant time, so the algorithm runs in O(log n).
ii. We can instead compute G, G2, G4, . . . by repeated squaring, and mul- tiply those terms which correspond to bits appearing in the binary representation of n. There are ⌊log2 n⌋ such terms to consider, so the algorithm again takes O(log n) time.
6. [A] Suppose you are given an array A containing 2n numbers. The only oper- ation that you can perform is make a query if element A[i] is equal to element A[j], 1 ≤ i,j ≤ 2n. Your task is to determine if there is a number which appears in A at least n times using an algorithm which runs in linear time.
Warning and a Hint: a tricky one. The reasoning resembles a little bit the reasoning used in the celebrity problem: try comparing them in pairs and first find one or at most two possible candidates and then count how many times they appear.
Solution: Create two arrays B and C, initially both empty. Repeat the following procedure n times:
• Pick any two elements of A and compare them.
– If the numbers are different, discard both of them.
– If instead the two numbers are equal, append one of them to B and the other to C.
Claim: If a value x appears in at least half the entries of A, then the same value also appears in at least half the entries of B.
Proof: Suppose such a value x exists. In a pair of distinct numbers, at most one of them can be x, so after discarding both, x still makes up at least half
the remaining array elements. Repeating this, x must account for at least half the values appearing in B and C together. But B and C are identical, so at least the entries of B are equal to x.
We can now apply the same algorithm to B, and continue reducing the instance size until we reach an array of size two. The elements of this array are the only candidates for the original property, i.e. the only values that could have appeared n times in the original array.
Finally we analyse the time complexity. Clearly, each step of the procedure repeated n times above takes constant time, so we can reduce the problem from array A (of length 2n) to array B (of length ≤ n) in Θ(n) time. Letting the instance size be half the length of the array (to more neatly fit the Master Theorem), we can express the worst case using the recurrence
T (n) = T n + Θ(n). 2
Now af(n/b) = f(n/2), which is certainly less than say 0.9f(n) for large n as f is linear. By case 3 of the Master Theorem, the time complexity is T(n) = Θ(f(n)) = Θ(n), as required.
7. [A]LetP(x)=a0+a1xandQ(x)=b0+b1x,anddefineR(x)=P(x)·Q(x). Find the coefficients of R(x) using only three products of pairs of expressions each involving the coefficients ai and/or bj.
Addition and subtraction of the coefficients do not count towards this total of three products, nor do scalar multiples (i.e. products involving a coefficient and a constant).
Solution: We use (essentially) the Karatsuba trick:
R(x) = (a0 + a1x)(b0 + b1x)
= a0b0 + (a0b1 + b0a1)x + a1b1x2
=a0b0 +[(a0 +a1)(b0 +b1)−a0b0 −a1b1]x+a1b1x2.
Note that the last expression involves only three multiplications: a0b0, a1b1 and (a0 + a1)(b0 + b1).
8. [A] Let P(x) = a0 +a1x+a2x2 +a3x3 and Q(x) = b0 +b1x+b2x2 +b3x3, and define R(x) = P (x) · Q(x). Find the coefficients of R(x) using only twelve products of pairs of expressions each involving the coefficients ai and/or bj.
Challenge: can you do better?
Solution: We again use the Karatsuba trick:
R(x)=(a0 +a1x+a2x2 +a3x3)(b0 +b1x+b2x2 +b3x3)
= (a0 + a1x)(b0 + b1x) + (a0 + a1x)(b2 + b3x)x2
+ (a2 + a3x)(b0 + b1x)x2 + (a2 + a3x)(b2 + b3x)x4
=a0b0 +[(a0 +a1)(b0 +b1)−a0b0 −a1b1]x+a1b1x2 +a0b2 +[(a0 +a1)(b2 +b3)−a0b2 −a1b3]x+a1b3x2x2 +a2b0 +[(a2 +a3)(b0 +b1)−a2b0 −a3b1]x+a3b1x2x2 +a2b2 +[(a2 +a3)(b2 +b3)−a2b2 −a3b3]x+a3b3x2x4.
Note that each of the last four lines involves only three multiplications. Ex- panding and regrouping will yield the coefficients of R(x).
It is actually possible to solve the problem using only seven multiplications! 9. [A] Recall that the product of two complex numbers is given by
(a + ib)(c + id) = ac + iad + ibc + i2bd = (ac−bd)+i(ad+bc)
(a) Multiply two complex numbers (a + ib) and (c + id) (where a, b, c, d are all real numbers) using only 3 real number multiplications.
(b) Find (a + ib)2 using only two multiplications of real numbers.
(c) Find the product (a + ib)2(c + id)2 using only five real number multiplica-
(a) This is again the Karatsuba trick:
(a + ib)(c + id) = ac − bd + (bc + ad)i
= ac − bd + [(a + b)(c + d) − ac − bd] i, so we need only 3 multiplications: ac and bd and (a + b)(c + d).
(b) We again expand and refactorise:
(a+ib)2 =a2 −b2 +2abi
= (a + b)(a − b) + (a + a)bi. 10
(c) Observe that
(a + ib)2(c + id)2 = [(a + ib)(c + id)]2.
Therefore, we can now use (a) to multiply (a + ib)(c + id) with only three multiplications and then use (b) to square the result with two additional multiplications.
10. [A] Suppose we modify the median of medians quickselect algorithm to use blocks of seven rather than five. Determine the appropriate worst-case recur- rence, and solve for the asymptotic growth rate.
Solution: We first recurse to find the median of the n7 block medians. That median is guaranteed to be greater than four elements in each of n blocks, and
less than four elements in each of n blocks. Therefore the worst case partition 14
is in a ratio of 2 : 5, and we may have to recursively select from 5n of the 7
original items. Therefore the recurrence is
T(n)=T 7 +T 7 +Θ(n).
• the two subproblems at the second level of the recursion have a total of
• the four subproblems at the third level of the recursion have a total of 36n 49
• and so on.
The total size of all subproblems is bounded above by
662 n n1+7+7 +…=1−6=7n,
so the total time taken (for forming and sorting blocks as well as partitioning) is Θ(n).
11. Given an array A of n distinct integers and an integer k < n2 , design an O(n) algorithm which finds the median as well as the k values closest to the median from above and below. You may assume that n is odd.
Solution: Apply median of medians quickselect to find the values k ranks
below and k ranks above the median, i.e. the n+1 − kth and n+1 + kth 22
smallest values. Then scan through the array, checking whether each element lies between these bounds.
12. Given two sorted arrays A and B, each of length n, design a O(log n) algorithm to find the (lower) median of all 2n elements of both arrays. You may assume that n is a power of two and that all 2n values are distinct.
Solution: If A[n/2] < B[n/2], then A[n/2] is smaller than the median, and B[n/2 + 1] is larger than the median. We can therefore discard the first half of A and the second half of B, and the median of the remaining n elements is our answer.
Similarly, if A[n/2] > B[n/2], we instead discard the second half of A and the first half of B.
We have transformed an instance of size n to an instance of size n/2 using only one comparison, so the recurrence is
T (n) = T n + Θ(1). 2
The critical exponent is c∗ = log2 1 = 0, so by case 2 of the Master Theorem, the asymptotic solution is T (n) = Θ(log n). Note that this is the same recurrence as binary search.
13. Let A be an array of n distinct integers, each with an associated weight wi. All wi are non-negative, and w1 + . . . + wn = 1. The weighted (lower) median is the element A[k] satisfying
wi<12and wi≤12. A[i]
Design a O(n) algorithm to find the weighted (lower) median.
Solution: The required algorithm is a small modification of median of medians quickselect. After partitioning, we compute the sum of weights of elements left of the pivot, and the sum of weights of those right of the pivot. If either is greater than 21, we recurse on that side. If both are at most 12, we stop.
The additional calculation takes linear time, which is the same as the work already performed to form and sort blocks and partition the array. Therefore, this modification does not worsen the time complexity.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com