首页 >
> 详细

CMPUT 204 Practice Test with Solutions

Question 1.

Consider array A = [3, 8, 5, 9, 2, 7, 6, 4].

Part (a)

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);

Part (b)

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

Part (c)

(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 < j.

When j = 5, i = 1 and the working array is [3, 8, 5, 9, 2, 7, 6, 4]. The assumption before the

iteration is: A[1] ≤ pivot and A[k] > pivot where k = 2, 3, 4. Now since A[j] ≤ pivot, according

to the Partition code, i = 2, and we exchange A[i] and A[j], which results in the working array

[3, 2, 5, 9, 8, 7, 6, 4]. The maintenance works because A[k] ≤ pivot for k = 1, 2, and A[k] > pivot for

k = 3, 4, 5 before the next iteration (more precisely, at the start of the next iteration).

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(12n2) is the

correct answer, even though 2n ∈ O(12n2) 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.

(A short justification: When n approaches infinity, the first term is approaching zero and the

second is approaching infinity.)

2. n4(log n)3 n3.99(log n)4

Answer. n4(log n)3 ∈ ω(n3.99(log n)4).

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.

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 ) + n

2 + n

Answer.

(i) T (n) ∈ Θ(n2).

(ii) Let a = 4, b = 3, and f(n) = n2 + n. We have T (n) = aT (nb ) + f(n), f(n) ∈ ?(nlogb a+)

for some ∈ (0, 2? logb a], and af(nb ) ≤ δf(n) for some δ ∈ ( ab2 , 1) and all sufficiently large n

(n ≥ (abδ)/(δab2 )). The Master Theorem (case 3) is applicable to this recurrence relation,

and it solves it to T (n) ∈ Θ(n2).

c) T (n) = T (n? 3) + 2 log n

Answer.

(i) T (n) ∈ Θ(n log n).

(ii) Without loss of generality, we suppose 3 | n. Using iterated substitution, we have

So we have T (n) ∈ O(n log n) and T (n) ∈ ?(n log n). We therefore have T (n) ∈ Θ(n log n).

Page 3

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.

Answer.

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 6= ?. Otherwise, continue binary search in S for the next

element T [i+ 1].

3. If we have T [i] 6∈ 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.

QuickSort(T, 1,m) takes O(m logm) operations. For each S[i] in S[1 . . . n], we use binary

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 logm operations. Totally, the time complexity is m logm + n logm ≤

2n logm ∈ O(n log logn).

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- Fit5217辅导、Python程序语言辅导 2022-05-31
- 辅导ecs 170 Introduction To Artificial... 2022-05-31
- 辅导ecs 170 Homework Assignment 5 2022-05-31
- Fit 5003 Software Security辅导 2022-05-30
- 辅导cse 101 Data Structures And Algori... 2022-05-30
- 辅导econ7150、辅导java，Python编程 2022-05-30
- Econ7150编程辅导 讲解 S1 2022 2022-05-29
- 讲解cse 101 程序 辅导 Data Structures 2022-05-29
- 辅导fit 5003 Software Security 2022-05-29
- Stat7055 Introductory Statistics For B... 2022-05-28
- Assignment 3 Description: Computer Sy... 2022-05-28
- 辅导laboratory 程序、辅导program编程 2022-05-28
- 讲解eece 1080C Programming For Ece 2022-05-28
- Comp10002 Foundations Of Algorithms辅导... 2022-05-28
- 辅导 Swen30006、辅导java/C++编程 2022-05-28
- Comp326讲解导、辅导python，Java程序 2022-05-28
- 辅导 Dungeon Crawler C++ - Assignment ... 2022-05-27
- 辅导mast30025 Linear Statistical Model... 2022-05-27
- Prog2002辅导、辅导sql语言编程 2022-05-26
- 辅导 Info411/911 Data Mining Knowledge... 2022-05-26