Algorithms - GATE Previous Year Questions

Question 1 Multiple Choice (Single Answer)

Suppose the letters a, b, c, d, e, f have probabilities $ \dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{8},\dfrac{1}{16},\dfrac{1}{32},\dfrac{1}{32}$ respectively.

What is the average length of the correct answer to Q.?

3
2.1875
2.25
1.9375

Question 2 Multiple Choice (Single Answer)

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

$\Theta(n)$
$\Theta(m)$
$\Theta(m+n)$
$\Theta(mn)$

Question 3 Multiple Choice (Single Answer)

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is

$\Theta(n)$
$\Theta(\log n)$
$\Theta(\log^*n)$
$\Theta(1)$

Question 4 Multiple Choice (Single Answer)

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?

3
4
5
6

Question 5 Multiple Choice (Single Answer)

G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

For every subset of k vertices, the induced subgraph has at most 2k-2 edges
The minimum cut in G has at least two edges
There are two edge-disjoint paths between every pair of vertices
There are two vertex-disjoint paths between every pair of vertices

Question 6 Multiple Choice (Single Answer)

Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to

only vertex a
only vertices a, e, f, g, h
only vertices a, b, c, d
all the vertices

Question 7 Multiple Choice (Single Answer)

Consider the following functions:
f(n) = 2ⁿ
g(n) = n!
h(n) = n^logn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

f(n) = O(g(n)); g(n) = O(h(n))
f(n) = $\Omega$(g(n)); g(n) = O (h(n))
g (n) = O(g(n)); h(n) = O(f(n))
h(n) = O(f(n)); g(n) = $\Omega$(f(n))

Question 8 Multiple Choice (Single Answer)

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W.
An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

Q solves the subset-sum problem in polynomial time when the input is encoded in unary
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
The subset sum problem belongs to the class NP
The subset sum problem is NP-hard

Question 9 Multiple Choice (Single Answer)

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

MNOPQR
NQMPOR
QMNPRO
QMNPOR

Question 10 Multiple Choice (Single Answer)

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

$T(n) \leq 2T(n/5) + n$
$T(n) \leq T(n/5) + T(4n/5) + n$
$T(n) \leq 2T(4n/5) + n$
$T(n) \leq 2T(n/2) + n$

Question 11 Multiple Choice (Single Answer)

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,….,n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

$\Theta(\log n)$
$\Theta(n)$
$\Theta(n\log n)$
None of the above, as the tree cannot be uniquely determined

Question 12 Multiple Choice (Single Answer)

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

$\Theta(\log n)$
$\Theta(n)$
$\Theta(n\log n)$
$\Theta(n^2)$

Question 13 Multiple Choice (Single Answer)

Consider the following C functions:

int f1(int n) {
  If(n == 0 | | n == 1)
  return n;
  else
    return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n) {
  int i;
  int X[N], Y[N], Z[N];
  X[0] = Y[0] = Z[0] = 0;
  X[1] = 1;
  Y[1] = 2;
  Z[1] = 3;
  for (i = 2; i <= n; i++) {
    X[i] = Y[i - 1] + Z[i - 2];
    Y[i] = 2 * X[i];
    Z[i] = 3 * X[i];
  }
  Return X[n];
}

f₁ (8) and f₂ (8) return the values

1661 and 1640
1640 and 1640
59 and 59
1640 and 1661

Question 14 Multiple Choice (Single Answer)

Consider the following C functions:

int f1(int n) {
  If(n == 0 | | n == 1)
  return n;
  else
    return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n) {
  int i;
  int X[N], Y[N], Z[N];
  X[0] = Y[0] = Z[0] = 0;
  X[1] = 1;
  Y[1] = 2;
  Z[1] = 3;
  for (i = 2; i <= n; i++) {
    X[i] = Y[i - 1] + Z[i - 2];
    Y[i] = 2 * X[i];
    Z[i] = 3 * X[i];
  }
  Return X[n];
}

The running time of f1 (n) and f2 (n) are

$\Theta$(n) and $\Theta$(n)
$\Theta$(2ⁿ) and $\Theta$(n)
$\Theta$(n) and $\Theta$(2ⁿ)
$\Theta$(2ⁿ) and $\Theta$ (2ⁿ)

Question 15 Multiple Choice (Single Answer)

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁, a₂, a₃, …,
a_n}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for
solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns.
X [i, j], 1$\le$i $\le$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a₁, a₂, …, a}
whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

X[1, W]
X[n, 0]
X[n, W]
X[n - 1, n]

Question 16 Multiple Choice (Single Answer)

Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search.
The program is erroneous.

1.         f(int Y[10], int x) {          
2.            int u, j, k;
3.            i = 0; j = 9;
4.           do {
5.               k = (i + j)/2;
6.               if (Y[k] ! = x) && (i < j);
7.            } while ((Y[k] ! = x) && (i <j));
8.            if (Y[k] == x) print f(“x is in the array”);
9.            else print f(“x is not in the array”);
10.       }

On which of the following contents of Y and x does the program fail?

Y is [1 2 3 4 5 6 7 8 9 10] and x <10
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

Question 17 Multiple Choice (Single Answer)

Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search.
The program is erroneous.

1.         f(int Y[10], int x) {          
2.            int u, j, k;
3.            i = 0; j = 9;
4.           do {
5.               k = (i + j)/2;
6.               if (Y[k] ! = x) && (i < j);
7.            } while ((Y[k] ! = x) && (i <j));
8.            if (Y[k] == x) print f(“x is in the array”);
9.            else print f(“x is not in the array”);
10.       }

The correction needed in the program to make it work properly is

Change line 6 to : if Y[k] < x) i = k + 1; else j = k - 1;
Change line 6 to : if Y[k] < x) i = k - 1; else j = k + 1;
Change line 6 to : if Y[k] <= x) i = k; else j = k;
Change line 7 to:} while ((Y[K] ==x) && (i < j));

Question 18 Multiple Choice (Single Answer)

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁, a₂, a₃, …,
a_n}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for
solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns.
X [i, j], 1$\le$i $\ge$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a₁, a₂, …, a}
whose elements sum to j.

Which of the following is valid for 2 $\le$ i $\le$ n and ai $\le$ j $\le$ W?

X[i, j] = X[i - 1, j] vX [i, j - a_i]
X[i, j] = X[i - 1, j] vX [i, 1, j - a_i]
X[i, j] = X[i - 1, j] $\land$X [i, j - a_i]
X[i, j] = X[i - 1, j] $\land$X [i-1, j - a_i]

Question 19 Multiple Choice (Single Answer)

What is the number of swaps required to sort n elements using selection sort, in the worst case?

$\theta(n)$
$\theta(n log\ n)$
$\theta(n^2)$
$\theta(n^2log\ n)$

Question 20 Multiple Choice (Single Answer)

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm?
P. Always finds a negative weighted cycle, if one exists.
Q. Finds whether any negative weighted cycle is reachable from the source.

P only
Q only
both P and Q
Neither P nor Q

Question 21 Multiple Choice (Single Answer)

Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

There is no polynomial time algorithm for $\pi_A$.
If $\pi_A$ can be solved deterministically in polynomial time, then P = NP.
If $\pi_A$ is NP-hard, then it is NP-complete.
$\pi_A$ may be un decidable.

Question 22 Multiple Choice (Single Answer)

In quick-sort, for sorting n elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

$\Theta(n)$
$\Theta(n \log n)$
$\Theta(n^2)$
$\Theta(n^2 \log n)$

Question 23 Multiple Choice (Single Answer)

The running time of an algorithm is represented by the following recurrence relation:

$T(n) = \begin{cases}
n & n \leq 3 \\
T(\frac{n}{3})+cn & \text{ otherwise }
\end{cases}$

Which one of the following represents the time complexity of the algorithm?

$\Theta(n)$
$\Theta(n \log n)$
$\Theta(n^2)$
$\Theta(n^2 \log n)$

Question 24 Multiple Choice (Single Answer)

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i, j] = l(i,j).
Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(I, j)?

All elements L should be initialized to 0 for the values of l(i, j) to be properly computed.
The values of l(i, j) may be computed in a row major order or column major order of L(M,N).
The values of l(i, j) cannot be computed in either row major order or column major order of L(M,N).
L[p, q] needs to be computed before L[r, s] if either p<r or q<s.

Question 25 Multiple Choice (Single Answer)

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m, n),
where an incomplete recursive definition for the function l(i, j) to compute the length of the LCS of X[m]
and Y[n] is given below:
l (i, j) = 0, if either i=0 or j=0
= expr1, if i,j>0 and X [i-1] = Y [j 1]
= expr2, if i,j>0 and X [i-1] = Y [j 1]

Which one of the following options is correct?

expr1 = l (i − 1, j) + 1
expr1 = l (i, j − 1)
expr2 = max (l (i − 1, j), l (i,j - 1))
expr2 = max (l (i − 1, j − 1), l (i, j))

Question 26 Multiple Choice (Single Answer)

Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?

(b,e) (e,f) (a,c) (b,c) (f,g) (c,d)
(b,e) (e,f) (a,c) (f,g) (b,c) (c,d)
(b,e) (a,c) (e,f) (b,c) (f,g) (c,d)
(b,e) (e,f) (b,c) (a,c) (f,g) (c,d)

Question 27 Multiple Choice (Single Answer)

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

| | |
|---|---|
| 0| |
| 1| |
| 2| 2|
| 3| 23|
| 4||
| 5| 15|
| 6||
| 7||
| 8| 18|
| 9||
|||
|---|---|
| 0||
| 1||
| 2| 12|
| 3| 13|
| 4||
| 5| 5|
| 6||
| 7||
| 8| 18|
| 9||
|||
|---|---|
| 0||
| 1||
| 2| 12|
| 3| 13|
| 4| 2|
| 5| 3|
| 6| 23|
| 7| 5|
| 8| 18|
| 9| 15|
|||
|---|---|
| 0 ||
| 1 ||
| 2 | 12,2 |
| 3 | 13,3,23 |
| 4 ||
| 5 | 5,15 |
| 6 ||
| 7 ||
| 8 | 18 |
| 9 ||