CSCI 570 Homework 5 Solution
1. Give the asymptotic running time of the following recurrences if they can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem
does not apply.
a. T(n) = 3T(n/3) +
b. T(n) = 2T(n/2)+nlogn. c. T (n) = 7T (n/3) + n2 + 2n. d. T(n) = 2nT(n/2) + nn.
e. T (n) = 7T (n/2) + n2 + 1.
Solution: a. T(n) = Θ(n) (Case 1). b. T(n) = Θnlog2 n (Case 2). c.
T(n) = Θn2 (Case 3). d. Does not apply. e. T(n) = Θnlog2 7 (Case 1).
2. Suppose you are given an ascending sorted array that is circularly rotated right. For example, [1,2,3,4,5] becomes [4,5,1,2,3] when rotated by 2 posi- tions. Give an algorithm that finds the smallest element in O(log n) time.
Solution: The divide-and-conquer algorithm is as follows: Input: a rotated array A of size n;
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12:
while A is not empty do
pick the k = ⌊n/2⌋ th element; ifA[k]
return A[k + 1]; elseifA[k]
A = A[k + 1 :]; end if
end while
√
n.
Since the size of array is at least halved in each recursion and the running time of each recursion is O(1), the total running time is O(log n).
3. Solve Kleinberg and Tardos, Chapter 5, Exercise 2. Solution: The algorithm is as follows:
Input: a sequence of numbers a1, a2, …, an;
Output: numberofsignificantinversionsN;ascendingsortedarraya′1,a′2,…,a′n;
1: if n = 1 then
2: return N = 0 and {a1};
1
3: 4: 5:
6:
7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18:
else
let k = ⌊n/2⌋;
call the algorithm on the a1 , …, ak and denote the result as N1 and b1, b2, …, bk;
call the algorithm on the ak+1,…,an and denote the result as N2 and bk+1, bk+2, …, bn;
◃ Subroutine for merging results of two parts. i←k,j←n,N3 ←0;
while i > 1 and j > k + 1 do
if bi ≤ 2bj then j ← j − 1;
else if bi > 2bj then N3 ← N3 + j − k; i ← i − 1;
end if end while
returnN=N1+N2+N3anda′1,…,a′n =MERGE(b1,…,bk;bk+1,…,bn); end if
This recursion follows T (n) = 2T (n/2)+n, so the total running time is O(n log n). 4. Solve Kleinberg and Tardos, Chapter 5, Exercise 3.
Solution: Denote the set of cards as S, the algorithm is as follows:
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22:
if |S| = 1 then return the card;
else if |S| = 2 then
if two cards are equivalent then
return either card;
end if else
let S1 be the first ⌊|S|/2⌋ cards and S2 be the remaining cards; call the algorithm recursively on S1;
if one card is returned then
if more than |S|/2 cards are equivalent to this card then return this card
else
call the algorithm recursively on S2 if one card is returned then
if more than |S|/2 cards are equivalent to the card then return this card
end if end if
end if end if
end if
This recursion follows T (n) ≤ 2T (n/2) + 2n, so the running time is T (n) = O(n log n).
2