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

G= (V,E)

be a directed graph with

n

vertices. A path from

v_i

v_j

G

is a sequence of vertices (

v_{i},v_{i+1}, \dots , v_j

(v_k, v_{k+1}) \in E

k

i

j-1

. A simple path is a path in which no vertex appears more than once. Let

A

n \times n

array initialized as follows: …

The following are the starting and ending times of activities

A, B, C, D, E, F, G

H

respectively in chronological order:

“a_s \: b_s \: c_s \: a_e \: d_s \: c_e \: e_s \: f_s \: b_e \: d_e \: g_s \: e_e \: f_e \: h_s \: g_e \: h_e”

x_s

denotes the starting time and

x_e

denotes the ending time of activity X. We need to schedule …

What is the weight of a minimum spanning tree of the following graph?

G =(V,E)

be an undirected graph with a subgraph

G_1 = (V_1, E_1)

. Weights are assigned to edges of

G

w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, otherwise} \end{cases}

A single-source shortest path algorithm is executed on the weighted graph

(V,E,w)

with an arbitrary vertex

v_1

V_1

as the source. …

In a permutation

a_1 ... a_n

, of n distinct integers, an inversion is a pair

(a_i, a_j)

i < j

a_i > a_j

. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of

1. . . n

Consider the following recurrence relation

T(1)=1

T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor

n \geq 1

T(m^2)

m \geq 1

\Theta(n^2)

implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depth-first traversals of the above graph?

Consider the following three claims:

(n+k)^m = \Theta(n^m)

k

m

2^{n+1} = O(2^n)

2^{2n+1} = O(2^n)

Which of the following claims are correct?

Ram and Shyam have been asked to show that a certain problem

\Pi

\text{NP-complete}.

Ram shows a polynomial time reduction from the

\text{3-SAT}

\Pi

, and Shyam shows a polynomial time reduction from

\Pi

\text{3-SAT.}

Which of the following can be inferred from these reductions?

Consider the following

C

function. For large values of

y

, the return value of the function

f

best approximates float f,(float x, int y) { float p, s; int i; for (s=1,p=1,i=1; i<y; i++) { p *= x/i; s += p; } return s; }

The cube root of a natural number

n

is defined as the largest natural number

m

(m^3 \leq n)

. The complexity of computing the cube root of

n

n

is represented by binary notation) is

The running time of the following algorithm Procedure

A(n)

n \leqslant 2

1

(A( \lceil \sqrt{n} \rceil))

; is best described by

Consider the following algorithm for searching for a given number

x

in an unsorted array

A[1..n]

n

distinct values: Choose an

i

1..n

A[i] = x

, then Stop else Goto 1; Assuming that

x

A

, what is the expected number of comparisons made by the algorithm before it terminates?

The solution to the recurrence equation

T(2^k) = 3T(2^{k-1})+1, T(1) =1

Consider an undirected, unweighted graph

G

. Let a breadth-first traversal of

G

be done starting from a node

r

d(r,u)

d(r,v)

be the lengths of the shortest paths from

r

u

v

respectively in

G

u

is visited before

v

during the breadth-first traversal, which of the following statements is correct?

f(n) = n^2 \log n

g(n) = n(\log n)^{10}

be two positive functions of

n

. Which of the following statements is correct?

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort?

G

be an undirected graph. Consider a depth-first traversal of

G

T

be the resulting depth-first search tree. Let

u

G

v

be the first new (unvisited) vertex visited after visiting

u

in the traversal. Which of the following statement is always true?

G

be an undirected connected graph with distinct edge weights. Let

e_{max}

be the edge with maximum weight and

e_{min}

the edge with minimum weight. Which of the following statements is false?