# GATE Questions & Answers of Algorithms Computer Science and Information Technology

#### Algorithms 114 Question(s) | Weightage 14 (Marks)

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ________.

Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0]. The subsequence sum $S\left(i,j\right)={\textstyle\sum_{k=i}^j}A\lbrack k\rbrack$ . Determine the maximum of $S\left(i,j\right),$ where $0\leq i\leq j<14.$ (Divide and conquer approach may be used.)

There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, …, An is

Let G be any connected, weighted, undirected graph.

I. G has a unique minimum spanning tree, if no two edges of G have the same weight.

II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Which of the above two statements is/are TRUE?

Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j| = 1.
Which of the statements above must necessarily be true?

Assume that multiplying a matrix $\style{font-family:'Times New Roman'}{G_1}$ of dimension $\style{font-family:'Times New Roman'}{p\times q}$ with another matrix $\style{font-family:'Times New Roman'}{G_2}$ of dimension $\style{font-family:'Times New Roman'}{q\times r}$ requires pqr scalar multiplications. Computing the product of n matrices $\style{font-family:'Times New Roman'}{G_\mathit1G_\mathit2G_\mathit3\mathit.\mathit.\mathit.G_\mathit n}$ can be done by parenthesizing in different ways. Define $\style{font-family:'Times New Roman'}{G_\mathit i\mathit\;G_{\mathit i\mathit+\mathit1}}$ as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain $\style{font-family:'Times New Roman'}{G_\mathit1G_\mathit2G_\mathit3G_\mathit4G_\mathit5G_\mathit6}$ using parenthesization $\left(G_\mathit1\left(G_\mathit2G_\mathit3\right)\right)\left(G_\mathit4\left(G_\mathit5G_\mathit6\right)\right)\mathit,G_\mathit2G_\mathit3\mathit\;$ and $G_\mathit5G_\mathit6$ are the only explicitly computed pairs.

Consider a matrix multiplication chain $\style{font-family:'Times New Roman'}{F_1F_2F_3F_4F_5,}$ where matrices $F_1,F_2,F_3,F_4$ and $F_5$ are of dimensions $2\times25,\;25\times3,\;3\times16,\;16\times1$, and $1\times1000,$ respectively. In the parenthesization of $\style{font-family:'Times New Roman'}{F_1F_2F_3F_4F_5}$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y + 10z = _____.

Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.

Consider the weights and values of items listed below. Note that there is only one unit of each item.
 Item number Weight (in Kgs) Value (in Rupees) 1 10 60 2 7 28 3 4 20 4 2 24

The task is to pick a subset of these items such that their total weight is no more than 11 Kg sand their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy.

The value of Vopt Vgreedy is ____________.

Consider the following function from positive integers to real numbers:

$\style{font-family:'Times New Roman'}{10,\;\sqrt n,\;n,\;\log_2n,\;\frac{100}n.}$

The CORRECT arrangement of the above functions in increasing  order of asymptotic complexity is:

Consider the following table:

 Algorithms Design Paradigms (P) Kruskal (i) Divided and conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall (iii) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

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

(I) Munimum 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?

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 _________

Match the algorithms with their time complexities:

 Algorithm Time complexity (P) Towers of Hanoi with n disks (i)$\style{font-family:'Times New Roman'}{\Theta(n^2)}$ (Q) Binary search given n stored numbers (ii)$\style{font-family:'Times New Roman'}{\Theta(n\;\log\;n)}$ (R) Heap sort given n numbers at the worst case (iii)$\style{font-family:'Times New Roman'}{\Theta(2^n)}$ (S) Addition of two n$\style{font-family:'Times New Roman'}\times$n matrices (iv)$\style{font-family:'Times New Roman'}{\Theta(\log\;n)}$

The Breadth First search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

Consider the recurrence function $\style{font-family:'Times New Roman'}{T(n)=\left\{\begin{array}{l}2T\;(\sqrt n)+1,\;\;\;\;n>2\\2,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0<n\leq2\end{array}\right.}$

Then T(n) in terms of  $\style{font-family:'Times New Roman'}\Theta$ notation is

Consider the following C function

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 $\theta$ notation is

Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for $a_n$?

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is .

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change

Q: Shortest path between any pair of vertices does not change

Consider the recurrence relation $\style{font-family:'Times New Roman'}{a_1=8,a_n=6n^2+2n+a_{n-1}.\mathrm{Let}\;a_{99}=K\times10^4.}$ The value of $K$ is __________.

Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry $W_{ij}$ in the matrix W.

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ________ .

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is _______.

G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

I. If e is the lightest edge of some cycle in G, then every MST of G includes e

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

I.    Quicksort runs in $\mathrm\Theta\left(\mathit n^\mathit2\right)$ time

II.   Bubblesort runs in $\mathrm\Theta\left(\mathit n^\mathit2\right)$ time

III.  Mergesort runs in $\mathrm\Theta\left(\mathit n\right)$ time

IV Insertion sort runs in $\mathrm\Theta\left(\mathit n\right)$ time

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Match the following:

 (P) Prim’s algorithm for minimum spanning tree (i) Backtracking (Q) Floyd – Warshal algorithm for all pairs shortest paths (ii) Greedy method (R) Mergesort (iii) Dynamic programming (S) Hamiltonian circuit (iv) Divide and conquer

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting $n\left(\geq2\right)$ numbers? In the recurrence equations given in the options below, $c$ is a constant.

Consider the following C program segment.

while(first <= last)
{
if(array[middle] < search)
first = middle + 1;
else if (array[middle] = = search)
found = TRUE;
else last = middle – 1;
middle = (first + last)/2;
}
if (first > last) notPresent = TRUE;

The cyclomatic complexity of the program segment is ______.

Let $a_n$ represent the number of bit strings of length $n$ containing two consecutive 1s. What is the recurrence relation for $a_n$?

Let $G=\left(V,\;E\right)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $G=\left(V,\;E\right)$ let $d\left(x\right)$ denote the shortest distance in $G$ from $s$ to $x.$ A breadth first search (BFS) is performed starting at $s.$ Let $T$ be resultant BFS tree. If $\left(u,\;v\right)$ is an edge of $G$ that is not in $T$ , then which one of the following CANNOT be the value of $d\left(u\right)-d\left(v\right)?$

An   algorithm   performs   (log N)1/2   find   operations,  N insert   operations,   (log N)1/2  delete operations, and (log N)1/2 decrease-key operations on a set of data items with keys drawn form a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best asymptotic complexity considering all the operations?

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _______.

Consider the following C function.
int fun1 (int n){
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i) {
p = 0;
for(j = n; j > 1; j = j/2)
++p;
for(k =1; k < p; k = k*2)
++q;
}
return q;
}

Which one of the following most closely approximates the return value of the function fun1?

An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Given below are some algorithms, and some algorithm design paradigms.

 1. Dijkstra’s Shortest Path i. Divide and Conquer 2. Floyd-Warshall algorithm to compute all pairs shortest path ii. Dynamic Programming 3. Binary search on a sorted array iii. Greedy design 4. Backtracking search on a graph iv. Depth-first search v. Breadth-first search

Match the above algorithms on the left to the corresponding design paradigm they follow.

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

Consider the equality $\sum\limits_{i=0}^ni^3=X$ and the following choices for X.

I.       $\theta \left({n}^{4}\right)$

II.       $\theta \left({n}^{5}\right)$

III.       $O\left({n}^{5}\right)$

IV.       $\Omega \left({n}^{3}\right)$

The equality above remains correct if X is replaced by

Given a hash table T with 25 slots that stores 2000 elements, the load factor $\alpha$ for T is ______.

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes______.

Suppose $c=\left\langle c\left[0\right],\;...,\;c\left[k-1\right]\right\rangle$ is an array of lengt $k$, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.

DOSOMETHING (c, a, n)
z ← 1
for i ← 0 to k – 1
do zz2mod n
if c[i] = 1
then z ← (z $\times$ a) mod n
return z

If $k=4,\;c=\left\langle1,\;0,\;1,\;1\right\rangle a=2$ and n = 8, then the output of DOSOMETHING (c, a, n) is _________.

Let (n) = n and g(n) = n(1+sin n), where n is a positive integer. Which of the following statements is/are correct?

I.  (n) = O(g(n))
II. (n) = $\Omega$(g(n))

Let G be a graph with n vertices and m edges.what is the tightest upper bound on the running time of depth first search on G, when G is represented as an adjecency matrix?

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtree having exactly 4 nodes is $O\left({n}^{a}{\mathrm{log}}^{b}n\right).$ Then the value of a+10b is _____.

Consider the directed graph given below.

which of the following is TRUE?

Let P be a quicksort program to sort numbers in ascendinng order using the first element as the pivot. Let t1 and t2 be the number of comparisions made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. which one of the following holds?

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

$T\left(n\right)=2T\left(\frac{n}{2}\right)+\mathrm{log}n$

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

Consider two strings A = qpqrr and B = pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

The number of distinct minimum spanning trees for the weighted graph below is _____

The minimum number of arithematic operation required to evaluate the polynomial $P\left(X\right)={X}^{5}+4{X}^{3}+6X+5$ for a given value of X,using only one temporary variable is_____.

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is 0(na logbn + mc logdn), the value of a + 10b + 100c + 1000d is ____.

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

The number of elements that can be sorted in Θ(log n) time using heap sort is

Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}

The return value of the function is

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?