GATE CS Algorithms questions

Practise Algorithms questions for GATE CS. Explore official PYQs and original subject-wise quizzes, check answers and view available solutions. Free, no sign-in.

Compare greedy choices, dynamic-programming states and graph algorithms. Identify the input size before analysing the time and space complexity of each solution.

20 on this page

SubjectTopicYearType

The pseudocode of a function

\text{fun ()}

is given below: fun(int A[0,....,n-1]) { for i=0 to n-2 for j=0 to n-i-2 if (A[j]>A[j+1]) then swap A[j] and A[j+1] } Let

A[0, \ldots, 29]

be an array storing

30

distinct integers in descending order. The number of swap operations that will be performed, if the function

\text{fun ()}

G(V, E)

be an undirected and unweighted graph with

100

d(u, v)

denote the number of edges in a shortest path between vertices

u

v

V

. Let the maximum value of

d(u, v), u, v \in V

u \neq v

30

T

be any breadth-first-search tree of

G

. Which ONE of the given options is CORRECT …

The maximum value of

\text{x}

such that the edge between the nodes

\text{B}

\text{C}

is included in every minimum spanning tree of the given graph is _________. (answer in integer)

In a double hashing scheme,

h_{1}(k)=k \bmod 11

h_{2}(k)=1+(k \bmod 7)

are the auxiliary hash functions. The size

m

of the hash table is

11

. The hash function for the

i

-th probe in the open address table is

\left[h_{1}(k)+i h_{2}(k)\right] \bmod m

. The following keys are inserted in the given order:

63,50,25,79,67,24

Consider the following algorithm someAlgo that takes an undirected graph

G

as input. someAlgo (G) Let

v

be any vertex in

G

G

v

u

G

at maximum distance from

v

as given by the BFS. Run BFS on

G

u

as the starting vertex. Let

z

be the vertex at maximum distance …

Consider an unorders list of

N

distinct integers. What is the minimum number of element comaparisons required to find an integer in the list that is NOT the largest in the list?

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph

G

\text{G}

be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant

\alpha

is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in

\text{G}

before and after the edge weight update?

A

n

with distinct elements is said to be bitonic if there is an index

1 \leq i \leq n

A[1 . . i]

is sorted in the non-decreasing order and

A[i+1 \ldots n]

is sorted in the non-increasing order. Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons …

Given an integer array of size

N

, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is

[82,101,90,11,111,75,33,131,44,93]

is heapified. Which one of the following options represents the first three elements in the heapified array?

Consider the following recurrence relation:

T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text{ for } n \geq 1, \\ 1 \quad \text{ for } n=1\end{array}\right.

Which one of the following options is CORRECT?

G

be a directed graph and

T

a depth first search

\text{(DFS)}

spanning tree in

G

that is rooted at a vertex

v

T

is also a breadth first search

\text{(BFS)}

G

v

. Which of the following statements is/are TRUE for every such graph

G

T

The number of edges present in the forest generated by the

\text{DFS}

traversal of an undirected graph

G

100

40

. The number of connected components in

G

\text{T(n)}

be the recurrence relation defined as follows:

\begin{array}{l} T(0)=1, \\ T(1)=2, \text{ and } \\ T(n)=5 T(n-1)-6 T(n-2) \text{ for } n \geq 2 \end{array}

Which one of the following statements is TRUE?

\text{A}

be an array containing integer values. The distance of

\text{A}

is defined as the minimum number of elements in

\text{A}

that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array

[2,5,3,1,4,2,6]

is ___________.

Consider an array

\mathrm{X}

\mathrm{n}

positive integers. A subarray of

\mathrm{X}

is defined to be a sequence of array locations with consecutive indices. The

\mathrm{C}

code snippet given below has been written to compute the length of the longest subarray of

\mathrm{X}

that contains at most two distinct integers. The …

The number of distinct minimum-weight spanning trees of the following graph is

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let

k

be the number of keys,

m

be the number of slots in the hash table, and

k>m

. Which one of the following is the best hashing strategy to counteract the adversary?

f

g

be functions of natural numbers given by

f(n)=n

g(n)=n^{2}.

Which of the following statements is/are

\text{TRUE}?