Algorithms Test 3

Number of Questions: 25 Section Marks: 30

Directions for questions 1 to 25: Select the correct alterna- 6. Consider the following:
tive from the given choices. I. If f(n) = O(g(n)) and g(n) = O(h(n)) then
1. Given the following input 564, 816, 726, 903, 1321, f(n) = W(h(n))
1345, 1498 and the Hash function is h(k) = k mod 3. II. The asymptotically tight upper bound for
Which of the following statements are CORRECT? T(n) = T(n – 2) + 1 is O(log n)
I. 564, 816, 726, 903 will hash to same Location. Which of the following is correct?
II. 1321, 1345, 1498 will hash to same Location. (A) I–TRUE, II–TRUE (B) I–TRUE, II–False
III. 816, 1345, 903 will hash to same Location. (C) I–False, II–TRUE (D) I–False, II–False
(A) I and III (B) I and II 7. Let
(C) II and III (D) I, II and III f(n) = 6n + 8n2 + 200n3,
2. Let M be an integer greater than 1. Which of the fol- g(n) = n2 log n
lowing represents the order of growth of the expression Which of the following is valid?
n (A) f(n) = O(g(n)) (B) f(n) = q(g(n))
∑ Mi as a function of ‘n’? (C) f(n) = W(g(n)) (D) g(n) = W(f(n))
i =1
8. If f(n) = n log n then which of the following is FALSE?
(A) q(nM) (B) q(M2n+1) (A) f(n) = O(n2 log n)
(C) q(Mn log n) (D) q(Mn) (B) f(n) = q (n log n)
(C) f(n) = W (n2)
Common Data For Questions 3 and 4: (D) f(n) = W (log n * log n)
To compute the Matrix product M1 M2, where M1 has
9. What is the average time complexity of the sequential
‘p’ rows and ‘q’ columns and M2 has ‘q’ rows and ‘r’ col-
search algorithm where the searched item is sequen-
umns, takes time proportional to ‘pqr’, and result is a matrix
tially compared to each element in the list of ‘n’
of ‘p’ rows and ‘r’ columns. Consider the given 5 matri-
elements?
ces, A1, A2, A3, A4 and A5 and their dimensions are P0 × P1,
n
P1 × P2, P2 × P3, P3 × P4, P4 × P5, respectively. The val- (A) (B) log n
ues are P0 = 10, P1 = 5, P2 = 15, P3 = 20, P4 = 40, 2
P5 = 25. n +1 n −1
(C) (D)
5 1 2 2
4 2 10. Consider the given data:
i
j 3 3 — Let n be the number of elements
Y 4 — Number of levels used in sorting: O(log n)
2 5 — At each level O(n) amount of work
The given data is related to:
1 X
(A) Heap sort (B) Merge sort
A4 A5 (C) Selection sort (D) Bubble sort
A3
A2 11. Consider a graph, with all distinct Edge weights, which
A1
of the following is TRUE?
(A) The shortest path is unique between every pair of
3. MATRIX-CHAIN-ORDER computes the rows from
vertices
bottom to top and from left to right, The value of X
(B) The maximal matching is unique
(where X = M[1, 2]) is ________
(C) The minimum spanning tree is unique
(A) 600 (B) 750
(D) All the above
(C) 800 (D) 900
12. The Hash function h(k) = k mod 7 with Linear probing
4. The value of Y (where Y = M[2, 4]) is ________.
is used to insert the keys 37, 38, 72, 68, 98, 11, 74 into
(A) 1500 (B) 5500
hash table indexed (0 – 6), The location of Key 74 is
(C) 15000 (D) None of the above
_________.
5. Which of the following cannot be the time complex- (A) 1 (B) 2
ity of Quick sort algorithm, under any of the Average, (C) 3 (D) 4
Best, Worst cases?
13. Given an undirected graph G = (V, E) and a posi-
(A) O(n log n) (B) O(n2)
3 tive integer ‘K’, does ‘G’ have ‘K’ vertices that form
(C) O(n ) (D) O(log n)
Algorithms Test 3 | 3.93

a complete sub graph and if it does, then what is the for (int j = 1; j < n; j * = 2){
minimum value of ‘K’? for (int k = 0; k < n; k + = 2){
(A) 2 (B) 3 sum + = (i + j * k);
}
(C) 4 (D) None of the above
}
14. In the Build-Heap algorithm, the Heapify routine }
is invoked ‘n’ times. This indicates that Build-Heap (A) O(n3)
Complexity is _____. (B) O(n2 log n)
(A) O(log n) (B) O (n) (C) O(log n * log n * log n)
(C) O(n log n) (D) O(n2) (D) O(n * log n * log n)
15. Give asymptotically tight Big-O bounds for the follow- 22. Consider the modified binary search algorithm so that
ing recurrence relations. (By using Iterative substitu- it splits the input not into 2 sets of sizes equal sizes, but
tion method) into three sets of sizes approximately one-third. What
T(n) = T(n – 2) + 1 if n > 2 is the recurrence for this ternary search algorithm?
T(n) = 1 if n ≤ 2
(A) T(n) = T   + T ( n − 2) + C
n
(A) O(n log n) (B) O(n) 2
(C) O(n2) (D) O(log n)
(B) T(n) = T   + C
n
16. Consider the given code:
public static int f2(int n){ 3

(C) T(n) = T   + T   + C
int x = 0; 3n n
for (int i= 0; i < n; i++)
 4  4
for (int j = 0; j < i * i; j++)
(D) T(n) = T   + log n
x++; n
return x; 3
}
What is the order of growth of the above code? 23. Sort the following growth rate classes in increasing
(A) O(log n) (B) O(n2) order of time complexity:
3
(C) O(n ) (D) O(2n) Exponential, quadratic, logarithmic, cubic, and facto-
rial.
17. Consider the following:
(A) Logarithmic, quadratic, cubic, exponential, facto-
I. (3n)! = O(n!3) II. log (n!) = q(n log n)
rial
Which of the following is correct?
(B) Logarithmic, quadratic, cubic, factorial, exponen-
(A) I–False, II–False (B) I–False, II–TRUE
tial
(C) I–TRUE, II–False (D) I–TRUE, II–TRUE
(C) Quadratic, cubic, logarithmic, exponential, facto-
18. The Floyd-Warshall all pairs shortest path algorithm rial
for finding the shortest distances between nodes in a (D) Quadratic, cubic, logarithmic, factorial, exponen-
graph is an example of: tial
(A) An iterative based divide - and - conquer
24. Determine if ‘x’ is present in an array of n-elements:
(B) A Dynamic programming formulation
for i = 0 to n
(C) A greedy algorithm if (a[i] = x) return TRUE
(D) A recursive based divide - and - conquer else
19. Which of the following is not having O(n2) complexity? return false
(A) n + 2000n (B) n1.999 What is the worst case, best case time complexities and
n3 space complexity respectively?
(C) 106n + 26n (D)
n (A) O(n), O(1), O(n)
(B) O(n), O(1), O(1)
20. Consider the given two strings str1 and str2. (C) O(n), O(log n), O(1)
Let str1 = < A B R A C A D A B R O A > (D) O(log n), O(log n), O(n)
str2 = < Y A B B A D A B B A D O O B A >
Then the length of longest common subsequence would 25. What is the space complexity of following sorting algo-
be ___________. rithms respectively?
(A) 5 (B) 6 I. Quick sort II. Merge sort
(C) 7 (D) 8 III. Selection sort IV. Insertion sort
(A) O(n), O(n), O(1), O(1)
21. What is the computational complexity of the following (B) O(1), O(n), O(1), O(n)
piece of code: (C) O(1), O(n), O(1), O(1)
for (i = n; i > 0; i/= 2){
(D) O(1), O(n), O(n), O(1)
3.94 | Algorithms Test 3

Answer Keys
1. B 2. D 3. B 4. B 5. D 6. D 7. C 8. C 9. C 10. B
11. C 12. A 13. A 14. D 15. B 16. C 17. A 18. B 19. D 20. D
21. D 22. B 23. A 24. B 25. C

Hints and Explanations

1. h(k) = k mod 3 M[5, 5] = 0
564 mod 3 = 0 M[1, 2] = min [M[i, k] + M[k + 1, j] + Pi–1 Pk Pj
i ≤k < j
816 mod 3 = 0
726 mod 3 = 0 K = 1 ⇒ M[1, 2] = M[1, 1] + M[2, 2]
903 mod 3 = 0 + P0 P1 P2
1321 mod 3 = 1 0 + 0 + 10 × 5 × 15
1345 mod 3 = 1 = 750 Choice (B)
1498 mod 3 = 1 4. M[2, 4] → The possible values for ‘K’ are 2, 3.
564, 816, 726, 903 will hash to same location, (1) M [2, 4] = M[2, 2] + M[3, 4] + P1 P2 P4
1321, 1345, 1498 will hash to same location. k =2

Statement III is not TRUE. Choice (B) (2) M [2, 4] = M[2, 3] + M[4, 4] + P1 P3 P4
k =3
2. Let M value be ‘3’
n We need to get the values of M[3, 4] and M[2, 3]
∑ 3i = 31 + 32 + 33... + 3n M [3, 4] = M[3, 3] + M[4, 4] + P2 P3 P4
k =3
i =1

The sequence is in Geometric Progression. 0 + 0 + 15 × 20 × 40 = 12000

First term =3=a M [2, 3] = M[2, 2] +M[3, 3] + P1 P2 P3
k =2
32
r = =3 = 0 + 0 + 5 × 15 × 20
3
= 1500
( r n − 1) Choose min of (1) and (2)
As r > 1 ⇒ sum = a M [2, 4] = M[2, 2] + M[3, 4] + P1 P2 P4
r −1
k =2
(3n − 1) 3(3n − 1)
3⋅ = 0 + 12000 + 5 × 15 × 40
3 −1 2 = 12000 + 3000 = 15000
3.3n − 3 * 1 3n +1 − 31 M [2, 4] = M[2, 3] + M[4, 4] + P1 P3 P4
= = k =3
2 2
= 1500 + 0 + 5 × 20 × 40
= 3n +1 ⇒ 3n (Ignore constants in Asymptotic Nota-
= 1500 + 4000 = 5500
tions ) \ M[2, 4] = min{15000, 5500} = 5500
\ q(Mn) is the order of growth of given expression.
Choice (B)
Choice (D)
5. Average and Best case time complexities are O(n log n)
3. Computing the matrix product Ai….k Ak+1….j takes Pi…l
and O(n log n)
Pk Pj scalar multiplications. Worst case time complexity is O(n2)
M[i, j]
Since (n log n) and n2 are less than n3, O(n3) is also
 0 if i = j  valid. Choice (D)
=  min {M [i , k ] + M [k + 1, j ] + P P P , if i < j}
i −1 k j
i ≤ k < j  6. I. f(n) = O(g(n)) and g(n) = O(h(n)) then
f(n) = W(h(n))
X = M[1, 2] Lets assume
i = 1, j = 2
f(n) = n
\ k=1 (\ i ≤ k < j)
g(n) = n2
P0 = 10, P1 = 5, P2 = 15, P3 = 20, h(n) = n3
P4 = 40, P5 = 25
f(n) ≤ g(n)
M[1, 1] = 0 ⇒ n ≤ n2
M[2, 2] = 0
g(n) ≤ h(n) ⇒ n2 ≤ n3
M[3, 3] = 0
Then f(n) ≥ h(n)
M[4, 4] = 0 ⇒ n ≥ n3 (false)
Algorithms Test 3 | 3.95

II. T(n) = T(n – 2) + 1 Maximal matching 2

Gives O(n) time complexity (False) Choice (D)
7. f(n) = 6n + 8n2 + 200n3 ⇒ n3
g(n) = n2 log n
Option (A):
Option (C)
n3 ≤ c * n2 log n (false) For any graph, there will be unique spanning tree.
Option (B): Choice (C)
n3 = c * n2 log n (false) 12. Hash function h(k) = k mod 7
Option (C): Given elements are: 37, 38, 72, 68, 98, 11, 74
n3 ≥ c * n2 log n (TRUE) Choice (C) 37 mod 7 = 2
38 mod 7 = 3
8. Option (A):
72 mod 7 = 2
n log n ≤ c * n2 log n (TRUE) 68 mod 7 = 5
Option (B): 98 mod 7 = 0
n log n = c * n log n (TRUE) 11 mod 7 = 4
Option (C): 74 mod 7 = 4
n log n ≥ c * n2 (False) Choice (C) 98 0
9. In an average case, the probability that ‘X’ is in the 74 1
Kth array slot is 1/n, hence the average number of com- 37 2
parisons is 38 3
n
1 n
∑  K × n  = n × ∑ K
1 72 4
i =1 k =1 68 5
1 n( n + 1) n + 1 11 6
= * = Choice (C)
n 2 2 Choice (A)
10. In the worst, average, best cases, merge sort procedure 13.
will have O(log n) levels. A B C
In each level O(n) work is required. Choice (B)
11. Option (A): B
A
b
2 3 It is a complete sub graph, with K = 2. Choice (A)
a 14. Heapify routine takes O(log n) time, if it is invoked ‘n’
c
times then Build Heap takes n * log n ⇒ O(n log n).
1 4
Choice (D)
d
15. Given Recurrence Relation:
\ There are 2 shortest paths From ‘a’ to ‘c’ T(n) = T(n – 2) + 1
1. a – b – c Assume n = 16
2. a – d –c T(16) = T(14) + 1
Option (B): T(14) = T(12) + 1
T(12) = T(10) + 1
T(10) = T(8) + 1
T(8) = T(6) + 1
T(6) = T(4) + 1
T(4) = T(2) + 1
T(2) = 1
Maximal matching 1 T(4) = 2
T(6) = 3
T(8) = 4
T(10) = 5
T(12) = 6
T(14) = 7
3.96 | Algorithms Test 3

T(16) = 8 20. str1 = A B R A C A D A B R O A

⇒ ⇒ O   ⇒ O(n)
n n
Choice (B)
2 2 str2 = Y A B B A D A B B A D O O B A
The longest common subsequence would be A B A D
16. Each iteration of the inner loop is quadratic in the outer
A B O A.
loop variable. The simplest way to do this is to realize
The length is ‘8’. Choice (D)
we are just summing Si2, which will just be O(n3), if we
use the integration trick. Choice (C) 21. In the outer for loop, the variable ‘i’ keeps halving, so it
goes a round (log n) times. For each ‘i’ next loop goes
17. Let us assume some value for n
round also (log n) times, because of doubling the vari-
n=5
n
I. (3 × 5)! = 15! = very large number able j. The inner most loop by ‘k’ goes round times.
(5!)3 = 1203 = 1728000 2
Loops are nested, so the bounds may be multiplied to
(3n)! < O(n!3)
give that the algorithm is O(n * log n * log n)
I–false
Choice (D)
II. log(n!) = q(n log n)
lets take n = 8 22. By analogy, we divide the elements instead of 2 sub-
log (n!) = log(8!) = log(40320) = 15.299 sets, we divide them into three subsets.
n log n = 24 n
\ T(n) = T   + c Choice (B)
log (n!) < (n log n) 3
II–false Choice (A)
23. logarithmic → log n
18. The Floyd-warshall all pairs shortest path algorithm in cubic → n3
a graph is an example of a dynamic programming for- quadratic → n2
mulation. Exponential → 2n
Choice (B) Factorial → n!
19. Option (A) logn < n2 < n3 < 2n < n!
n + 2000n ≤ c * n2 Logarithmic, quadratic, cubic, exponential, Factorial.
⇒ n ≤ c * n2 (TRUE) Choice (A)
Option (B) 24. The procedure given in problem performs linear search,
n1.999 ≤ c * n2 (TRUE) Worst case ⇒ O(n)
Option (C) Best case ⇒ O(1)
106n + 26n ≤ c * n2 We do not require extra space to search for an element
n ≤ c * n2 (TRUE) in an array, so space complexity is O(1). Choice (B)
Option (D)
25. Quick sort, selection sort, insertion sort are ‘In-place’
n3
≤ c * n2 (False) algorithms means they do not take extra space.
n \ O(1), O(1), O(1)
n2.5 ≤ c * n2(False) Merge sort is Not In-Place algorithm.
\ for a very large value of ‘n’ It needs extra space
Choice (D) \ O(n). Choice (C)