PAPER CODE NO. EXAMINER: Prof. Piotr Krysta Tel. No. 795 4266
COMP202 DEPARTMENT: Computer Science
HALF TERM EXAM: CLASS TEST 2018/19
Complexity of Algorithms
TIME ALLOWED : 50 minutes
INSTRUCTIONS TO CANDIDATES
NAME OF CANDIDATE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . STUD. ID . . . . . . . . . . . . . . . .
USUAL SIGNATURE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
READ THE FOLLOWING CAREFULLY:
1. This class test has two parts, Part A and Part B. Answer ALL questions in both parts.
NB: Maximum possible points = 50. NB: Exam contributes 10% to overall course mark.
2. In Part A, there are 8 questions and each question comprises 5 statements, for which you
should select the one most appropriate answer by placing a tick in the appropriate box.
3. Enter your name, examination number and yout student ID, IN PENCIL on the computer
answer sheet according to the instruction on that sheet. The digits should be entered in the
boxes under ‘Student ID Number’ and entered by means of horizontal lines in the appropriate
boxes underneath, exactly as when answering questions.
4. When you have completed Part A of this exam paper, read the instructions on the computer
answer sheet carefully and transfer your answers from the exam paper with a HB pencil.
5. In Part B, there are 2 questions. Write down your solutions to these questions in the provided
examination booklet.
6. At the end of the examination, be absolutely sure to hand in this exam paper AND the
computer answer sheet AND the examination booklet.
PAPER CODE COMP202 page 1 of 6 Continued
Part A:
Remark: In questions 1–4 below we assume that T (n) = c for n ≤ d , for some constants c
and d .
The following two questions 1–2 are about the following recurrence relation
T (n) = 16T (n/4) + n3.
We use the Master Method with a = 16,b = 4, so logb a = log4 16 = 2. Hence n
logb a = n2. Now
we have that f (n) = n3 = Ω(n2+) with, for instance, = 0.5.
1. [4 marks] Which calculation is then correct:
A. Then, af (n/b) = 16f (n/4) = 16 · (n/4)3 = 1643 f (n) = δf (n), so we are in Case 1 of the
Master Method with δ = 1643 =
1
4 < 5.
B. Then, there is a constant k ≥ 0 such that f (n) = n3 is O(nlogb a logk n), so we are in Case
2 of the Master Method.
C. Then, for any constant k ≥ 0 we have that f (n) = n3 is O(nlogb a logk n), so we are in
Case 2 of the Master Method.
D. Then, there is a constant k ≥ 0, for instance k = 5, such that f (n) = n3 isΩ(n2+logb a logk n),
so we are in Case 1 of the Master Method.
E. Then, af (n/b) = 16f (n/4) = 16 · (n/4)3 = 1643 f (n) = δf (n), so we are in Case 3 of the
Master Method with δ = 1643 =
1
4 < 1.
2. [4 marks] Based on the correct calculation from Question 1 we have that:
A. T (n) is Θ(n4)
B. T (n) is Θ(n3)
C. T (n) is Θ(n3 logn)
D. T (n) is Θ(n16/4)
E. T (n) is Θ(n3 log2 n)
PAPER CODE COMP202 page 2 of 6 Continued
The following two questions 3–4 are about the following recurrence relation
T (n) = 27T (n/3) + n3 logn.
We use the Master Method with a = 27,b = 3, so logb a = log3 27 = 3. Hence n
logb a = n3.
3. [4 marks] Which calculation is then correct:
A. Then, we have that f (n) = n3 logn = Ω(nlogb a−) with, for instance, = 1, so we are in
Case 2 of the Master Method.
B. Then, we have that f (n) = n3 logn = O(nlogb a−) for = 1, so we are in Case 3 of the
Master Method.
C. Then, af (n/b) = 27f (n/3) = 27 · (n/3)3 log(n/3) = (n)3 log(n/3) = f (n), so we are in Case
3 of the Master Method with δ = 1.
D. Then, we have that f (n) = n3 logn = Θ(nlogb a logk n), with k = 1, so we are in Case 2 of
the Master Method.
E. Then, we have that f (n) = n3 logn = O(nlogb a−) with, for instance, = 1, so we are in
Case 2 of the Master Method.
4. [4 marks] Based on the correct calculation from Question 3 we have that:
A. T (n) is Θ(n3)
B. T (n) is Θ(n3 log3 n)
C. T (n) is Θ(n3 log2 n)
D. T (n) is Θ(n2 logn)
E. T (n) is Θ(n4)
The following three questions 5–7 are about the fractional knapsack problem.
5. [4 marks] An instance of the Fractional Knapsack Problem is given by a set, S, of items,
where item i has weight wi and benefit bi , and there is a maximum allowed weight W . Then
the Fractional Knapsack Problem asks the following question:
A. Question: Find a setting for variables xi (one for each item i), where 0 ≤ xi ≤ wi that
maximizes
∑
i∈S bi , without exceeding the maximum weight W , i.e., where
∑
i∈S xi ≤W .
B. Question: Find a setting for variables xi (one for each item i), where 0 ≤ xi ≤ wi that
maximizes
∑
i∈S bixi , without exceeding the maximum weight W , i.e., where
∑
i∈S xi ≤
W .
C. Question: Find a setting for variables xi (one for each item i), where 0 ≤ xi ≤ wi that
maximizes
∑
i∈S bixi , without exceeding the maximum weight W , i.e., where
∑
i∈S wi ≤
W .
D. Question: Find a setting for variables xi (one for each item i), where 0 ≤ xi ≤ wi that
maximizes
∑
i∈S bi
xi
wi
, without exceeding the maximum weight W , i.e., where
∑
i∈S xi ≤
W .
E. Question: Find a setting for variables xi (one for each item i), where 0 ≤ xi ≤ wi that
maximizes
∑
i∈S wi , without exceeding the maximum weight W , i.e., where
∑
i∈S wi ≤
W .
PAPER CODE COMP202 page 3 of 6 Continued
6. [4 marks] Solve the following instance of the fractional knapsack problem. The maximum
allowable total weight is Wmax = 11.
item a b c d e
benefit 10 10 12 3 8
weight 4 5 3 2 2
Then, the following is true about the greedy algorithm to optimally solve this problem:
A. The greedy algorithm considers the items in the following order: e, c,a,b,d .
B. The greedy algorithm considers the items in the following order: d ,b,a, c,e.
C. The greedy algorithm considers the items in the following order: e, c,d ,b,a.
D. The greedy algorithm considers the items in the following order: d ,b,a, c,e.
E. The greedy algorithm considers the items in the following order: a,b, c,d ,e.
7. [4 marks] Given the correct order of the greedy algorithm from Question 6:
A. The greedy algorithm completely includes into the final solution items d ,b,a and only
1/3 fraction of c and the total benefit of the solution is 27.
B. The greedy algorithm completely includes into the final solution items e, c,a and only
3/5 fraction of b and the total benefit of the solution is 36.
C. The greedy algorithm completely includes into the final solution items e, c,a and only
2/5 fraction of b and the total benefit of the solution is 34.
D. The greedy algorithm completely includes into the final solution items d ,b,a and the
total benefit of the solution is 23.
E. The greedy algorithm completely includes into the final solution items a,b, c and the
total benefit of the solution is 32.
8. [4 marks] What statement is true about the data structure (2, 4)-tree:
A. It is a tree whose each internal node has at least 1 and at most 3 children.
B. It is a tree whose each internal node has exactly 2 children.
C. It is a tree whose each internal node has at least 2 and at most 4 children.
D. It is a tree whose each internal node has at least 1 and at most 2 children.
E. It is a tree whose each internal node has exactly 4 children.
PAPER CODE COMP202 page 4 of 6 Continued
Part B:
9. Maximum sum subarray problem is the following problem: We are given an array A[1, ... , n] of
integers (positive and negative), and the goal is to compute a subarray A[i∗, j∗] with maximum
sum, where 1 ≤ i∗ ≤ j∗ ≤ n. More precisely, if
s(i , j) =
j∑
k=i
A[k ] = A[i ] + A[i + 1] + · · · + A[j ],
denotes the sum of the subarray A[i , j ], then we want to find the indices 1 ≤ i∗ ≤ j∗ ≤ n such
that
s(i∗, j∗) = max{s(i , j) : 1 ≤ i ≤ j ≤ n}.
For example, if n = 8 and A[1, 2, 3, 4, 5, 6, 7, 8] = [3,−4, 6,−1,−1, 5,−3, 2], then the maxi-
mum sum is s(i∗, j∗) = 9 and is achieved for subarray A[3, 6] = A[i∗, j∗] = [6,−1,−1, 5].
(a) [5 marks]Design a divide and conquer algorithm that solves this problem in time O(n logn).
(b) [4 marks] Give an argument that your algorithm indeed has running time O(n logn) by
formulating an appropriate recurrence equation and solving it.
Solution: A subarray A[i∗, j∗] with maximum sum is:
• Either contained entirely in the first half of array A, i.e., j∗ ≤ n/2,
• Or it is contained entirely in the right half of A, i.e., i∗ ≥ n/2,
• Or it overlaps with both halves of A, that is, i∗ ≤ n/2 ≤ j∗.
We can compute the best subarray of the first two types with two recursive calls on the left
and right half of A. The best subarray of the third type consists of the best subarray that ends
at n/2 and the best subarray that starts at n/2. We can compute these by a straightforward
algorithm in O(n) time. Then, the recursive algorithm returns the subarray wigth the maximum
sum of these three subarrays.
Therefore, if T (n) denotes the running time of this recursive algorithm, then the following is
the recurrence equation for T : T (n) = 2T (n/2) + c · n where c is a fixed constant. We use
the Master Method and we see that if fulfils Case 2 with k = 0, and therefore the solution is
T (n) = Θ(n logn).
10. We will develop a recurrence solution to the following problem: How many different ways are
there to climb n stairs, if you can either step up one stair or hop up two steps? For example,
there are five different ways to climb four stairs: 1. step, step, step, step; 2. hop, hop; 3. hop,
step, step; 4. step, hop, step; 5. step, step, hop.
Let f (n) denote the number of different ways to climb n stairs. For example f (4) = 5 in the
example above.
(a) [4 marks] Find explicit values of f (1), that is, the number of ways to climb one step, and
f (2), that is, the number of ways to climb two steps.
PAPER CODE COMP202 page 5 of 6 Continued
(b) [5 marks] Then derive a recurrence relation for f (n) in terms of f (n − 1) and f (n − 2) for
each integer n ≥ 3. Give an argument justifying your derivation.
Solution: As special cases, there is 1 way to climb 1 stair (do one step), thus we have
f (1) = 1. Also there are two ways to climb 2 steps: step, step and hop; therefore f (2) = 2.
In general, an ascent of n stairs consists of either a step followed by an ascent of the re-
maining n − 1 stairs or a hop followed by an ascent of n − 2 stairs. So the total number of
ways to climb n stairs is equal to the number of ways to climb n− 1 stairs plus the number of
ways to climb n−2. This reasoning defines a recurrence: f (n) = f (n−1)+f (n−2), for any n ≥ 3.
PAPER CODE COMP202 page 6 of 6 End