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

previous year question of ALGORITHMS gate 1993

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

Answer : b)

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

AlgorithmsDesign Paradigms
(P)Kruskal(i) divide and conquer
(Q)Quicksort(ii) Greedy
(R)floyd-warshall(iii) Dynamic Programming

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)

Answer : c)
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)

Answer : a)

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

Answer : a)
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)

Answer : c)

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

Answer : b)

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)

Answer : c)

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

Answer : a)

OS – GATE Previous Year Questions
DS – GATE Previous Year Questions


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *