CMPUT 204 Practice Test with Solutions Consider array A = [3, 8, 5, 9, 2, 7, 6, 4].
To sort the array A by the call MergeSort(A, 1, 8), how many recursive calls to MergeSort are made? Show the first four such calls.
Answer. If MergeSort(A, 1, 8) itself is counted, then totally 15 calls to MergeSort are made. The first four such calls are as follows.
MergeSort(A, 1, 8); MergeSort(A, 1, 4); MergeSort(A, 1, 2); MergeSort(A, 1, 1);
Copyright By PowCoder代写 加微信 powcoder
Show the resulting array by the call Build-Max-Heap(A), with the original array A above.
Answer. Build-Max-Heap(A) returns [9, 8, 7, 4, 2, 5, 6, 3].
(i) Show the resulting array by the call Partition(A, 1, 8), with the original array A.
(ii) What loop invariant does the procedure Partition maintain? In your work for question (i), use the iteration at j = 5 (and therefore A[j] = 2) to explain how the maintenance works in this case.
Answer. (i) Partition(A, 1, 8) returns [3, 2, 4, 9, 8, 7, 6, 5]
(ii) Loop invariant: Note that the call to partition is Partition(A, p, r) with pivot = A[r].
LI: At the start of each iteration j,
A[p..i] holds original keys ≤ pivot,
A[i + 1..(j − 1)] holds original keys > pivot, and i
Question 2.
For each pair of functions below, indicate their relation in terms of orders of growth using the notations O(·), o(·), Θ(·), Ω(·), or ω(·). Use the most precise notation, e.g., 2n ∈ o(21n2) is the correct answer, even though 2n ∈ O(21n2) is not wrong (but it is a wrong answer for this question). No proof or justification is needed. If the two functions cannot be related in this way, just say so.
Below, answers are accompanied with detailed justifications for the convenience of your study. Page 1
Question 1.
2+n8 √n Answer. 2 + n8 ∈ o(√n).
(A short justification: When n approaches infinity, the first term is approaching zero and the second is approaching infinity.)
n3.99(log n)4
(nε grows faster than log n, for any small but positive ε.)
n4(log n)3
Answer. n4(log n)3 ∈ ω(n3.99(log n)4).
2+n8 2 8 lim √ = lim √ + lim √
n→∞ n n→∞ n n→∞n· n =0+0
n4(log n)3 n0.01 lim 3.99 4 = lim
Answer. nn ∈ o(2n2 ).
(Transform n to 2log n, and then work it out from there.)
n→∞ n (log n) n→∞ log n = ∞.
nn (2log n)n lim 2n2 = lim 2n2
n→∞ n→∞ =lim 1
n→∞ 2n2−nlogn = 0.
4. 2n √n+n log n
Answer. 2n ∈ ω(√n + n ). log n
(Let 2n = n + n. Then each n grows faster than the corresponding term in the second expression.)
lim√2n =lim 2 n→∞n+n n→∞√1+1
Question 3.
Find asymptotic tight bounds (i.e. Θ) for the following recurrences. Assume that in each case, T (n) is some positive constant for sufficiently small n. Your answer should consist of two parts (i) a Θ-bound, and (ii) a brief justification. If you apply the master theorem, indicate which case; if you use iterated substitution, give derivations leading to your conclusion; if you use a recurrence tree, draw such a tree and briefly explain it. In any case, you do not need to prove that your closed-form is correct.
a)T(n)=3T(n2)+n2 +1
(i) T (n) ∈ Θ(nlog2 3).
(ii)Leta=3,b=2,andf(n)= n2+1. WehaveT(n)=aT(nb)+f(n),andf(n)∈O(nlogba−ε) for some ε ∈ (0, logb a]. The Master Theorem (case 1) is applicable to this recurrence relation, and it solves it to T(n) ∈ Θ(nlog2 3).
b) T (n) = 4T ( n3 ) + n2 + n
(i) T(n) ∈ Θ(n2).
(ii)Leta=4,b=3,andf(n)=n2+n. WehaveT(n)=aT(nb)+f(n),f(n)∈Ω(nlogba+ε)
for some ε ∈ (0,2−log a], and af(n) ≤ δf(n) for some δ ∈ ( a ,1) and all sufficiently large n bb b2
(n ≥ (a −δ)/(δ− a )). The Master Theorem (case 3) is applicable to this recurrence relation, b b2
and it solves it to T(n) ∈ Θ(n2). c) T (n) = T (n − 3) + 2 log n
(i) T (n) ∈ Θ(n log n).
(ii) Without loss of generality, we suppose 3 | n. Using iterated substitution, we have
On the other hand, we have,
T (n) = T (n − 3) + 2 log n
= T (n − 6) + 2 log (n − 3) + 2 log n
= T (0) + 2 · log(3k)
≤ T (0) + 2n · log n
3 ∈ O(n log n).
T(n)=T(0)+2· log(3k)+ log(3k)
k=1 k=n6 +1 n
≥T(0)+2· log(3k) k=n6 +1
≥ T (0) + n3 · log n2 ∈ Ω(n log n).
So we have T(n) ∈ O(nlogn) and T(n) ∈ Ω(nlogn). We therefore have T(n) ∈ Θ(nlogn).
Question 4.
We are given two sets of integers S (with size n) and T (with size m). We want to find out if S and T are disjoint, i.e. if S ∩ T = ∅.
Part (a) [6 marks]
Suppose that m ≤ n. Describe a simple algorithm that takes O(n log n) time (briefly justify the
running time). You do not have to give a pseudocode in your description.
1. Sorting S[1..n] in ascending order, which takes O(n log n) time.
2. For each T [i] in T [1..m], using binary search in S to determine whether T [i] ∈ S or not. If T [i] ∈ S, then terminate and return S ∩ T ̸= ∅. Otherwise, continue binary search in S for the next element T [i + 1].
3. If we have T [i] ̸∈ S for every T [i] in T [1 . . . m], then return S ∩ T = ∅.
The step 2 will repeat at most m times, and each binary search in S takes O(log n) time. So the total running time is at most n log n + m log n ≤ 2n log n ∈ O(n log n).
Part (b) [8 marks]
Suppose that m is substantially smaller than n, say m ∈ O(log n). Give an algorithm that takes only O(n log log n) time (briefly justify the running time). Your algorithm should be given in a pseudocode, in which any algorithm from the textbook or lecture notes can be called directly without showing the code.
Answer. The pseudocode of the algorithm is as follows, Checking whether S ∩ T = ∅
**Precondition: S[1 . . . n], T [1 . . . m] are two arrays of integers. **Postcondition: Returns whether S ∩ T = ∅ or not.
if (n = 0 or (m = 0) return S ∩ T = ∅
QuickSort(T , 1, m) for i from 1 to n
l = 1, r = m
while l ≤ r
mid = l+r
if T [mid] > S[i] r = mid − 1
else if T [mid] < S[i] l = mid + 1
return S ∩ T ̸= ∅
end while end for
return S ∩ T = ∅ end if
QuickSort(T, 1, m) takes O(m log m) operations. For each S[i] in
search in T to determine whether S[i] ∈ T or not. This will repeat at most n times, and each binary search in T takes log m operations. Totally, the time complexity is m log m + n log m ≤ 2nlogm ∈ O(nloglogn).
S[1 . . . n],
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com