# ALGORITHMS |Gate-2017| Previous Year Questions| Set-4 ALGORITHMS |Gate-2017|

1. Consider the following functions from positives integers to real numbers

10,√n,n, log2n, 100/n

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is: [GATE -2017]

a. log2n,100/n,10, √n,n
b. 100/n,10, log2n, √n,n
c. 10, 100/n, √n, log2n,n
d. 100/n, log2n,10, √n,n

2. Consider the following table : [GATE -2017]

Match the algorithm to design paradigms they are based on:

a. (P)↔(ii), Q↔(iii), (R)↔(i)
b. (P)↔(iii), Q↔(i), (R)↔(ii)
c. (P)↔(ii), Q↔(i), (R)↔(iii)
d. (P)↔(i), Q↔(ii), (R)↔(iii)

ALGORITHMS |Gate-2017|

3. Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:

(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.

Which of the above statements is/are necessarily true? [GATE – 2017]

a. (I) only
b. (II) only
c. both (I) and (II
d. neither (I) nor (II)

4. Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________. [GATE – 2017]

a. 5
b. 6
c. 7
d. 8

ALGORITHMS |Gate-2017|

5. Match the algorithms with their time complexities: [GATE – 2017]

Algorithm                                     Time complexity

(P) Towers of Hanoi with n disks                       (i) Θ(n2)
(Q) Binary search given n stored numbers              (ii) Θ(n log⁡ n)
(R) Heap sort given n numbers at the worst case      (iii) Θ(2n)
(S) Addition of two n×n matrices                      (iv) Θ(log⁡ n)

a. P→(iii), Q→(iv), R→(i), S→(ii)
b. P→(iv), Q→(iii), R→(i), S→(ii)
c. P→(iii), Q→(iv), R→(ii), S→(i
d. P→(iv), Q→(iii), R→(ii), S→(i)

6. Consider the recurrence function Then T(n) in terms of Θ notation is :  [GATE – 2017]

a. Θ(log⁡log⁡n)
b. Θ(log⁡n)
c. Θ(√n)
d. Θ(n)]

7. Consider the following C function. [GATE – 2017]

int fun (int n)   {
int i, j;
for (i = 1; i <= n; i++)   {
for (j = 1; j < n; j += i)   {
printf(“%d %d”,i,j);
}
}}

Time complexity of fun in terms of Θ notation is

a. Θ(n√n)
b. Θ(n2 )
c. (n log⁡n)
d. Θ(n2 logn)

8. A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________. [GATE – 2017]

a. 225
b. 226
c. 227
d. 228