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

Consider functions

\textsf{Function\_1}

\textsf{Function\_2}

expressed in pseudocode as follows: Function_1 while n>1 do for i=1 to n do x = x + 1; end for n = ⌊n/2⌋; end while Function_2 for i = 1 to 100 * n do x = x + 1; end for Let

f_{1}(n)

f_{2}(n)

denote the number of times the statement

\textsf{“x = x + 1”}

is executed in …

U=\{1,2,3\}

2^{U}

denote the powerset of

U

. Consider an undirected graph

G

whose vertex set is

2^{U}

A, B \in 2^{U},(A, B)

G

if and only if (i)

A \neq B

, and (ii) either

A \subsetneq B

B \subsetneq A

. For any vertex

A

G

, the set of all possible orderings in which the …

Which one of the following statements is

\text{TRUE}

for all positive functions

f(n)?

Suppose we are given

n

m

hash table slots, and two simple uniform hash functions

h_{1}

h_{2}.

Further suppose our hashing scheme uses

h_{1}

for the odd keys and

h_{2}

for the even keys. What is the expected number of keys in a slot?

Consider a simple undirected weighted graph

\textit{G},

all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of

\textit{G}

\text{TRUE}?

\textit{G(V,E)}

be a directed graph, where

\textit{V} = \{ 1, 2, 3, 4, 5 \}

is the set of vertices and

\textit{E}

is the set of directed edges, as defined by the following adjacency matrix

\textit{A}.

A [i][j] = \left\{\begin{matrix} 1, & 1 \leq j \leq i \leq 5 \\ 0, & \text{otherwise}\end{matrix}\right.

A[i][j] = 1

Consider the following three functions.

f_1=10^n\quad f_2=n^{\log n}\quad f_3=n^{\sqrt {n}}

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

Consider the following array.

\begin{array}{|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array}

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is ___________.

Consider the following recurrence relation.

T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.

Which one of the following options is correct?

R_n

to be the maximum amount earned by cutting a rod of length

n

meters into one or more pieces of integer length and selling them. For

i>0

p[i]

denote the selling price of a rod whose length is

i

meters. Consider the array of prices: …

\textit{dynamic}

hashing approach for

4

-bit integer keys: There is a main hash table of size

4

2

least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to …

Consider the following

\text{ANSI C}

function: int SimpleFunction(int Y[], int n, int x) { int total = Y[0], loopIndex; for (loopIndex=1; loopIndex<=n-1; loopIndex++) total=x*total +Y[loopIndex]; return total; } Let

\textsf{Z}

10

\textsf{Z}[i]=1

i

0 \leq i \leq 9

. The value returned …

G

be a connected undirected weighted graph. Consider the following two statements.

S_1

: There exists a minimum weight edge in

G

which is present in every minimum spanning tree of

G

S_2

: If every edge in

G

has distinct weight, then

G

has a unique minimum spanning tree. Which one of the following options is correct?

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size

n

Consider the following

\text{ANSI C}

function: int SomeFunction (int x, int y) { if ((x==1) || (y==1)) return 1; if (x==y) return x; if (x > y) return SomeFunction(x-y, y); if (y > x) return SomeFunction (x, y-x); } The value returned by

\textrm{SomeFunction(15, 255)}

Consider the string

\textrm{abbccddeee}

. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is …

a \geq 1

b>1

, consider the following recurrence defined on the non-negative integers:

T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)

Which one of the following options is correct about the recurrence

T(n)

Consider the following directed graph: Which of the following is/are correct about the graph?

Consider the following

\text{ANSI C}

program #include <stdio.h> int foo(int x, int y, int q) { if ((x<=0) && (y<=0)) return q; if (x<=0) return foo(x, y-q, q); if (y<=0) return foo(x-q, y, q); return foo(x, y-q, q) + foo(x-q, y, q); } int main( ) { int r = foo(15, 15, 10); printf(“%d”, r); return 0; } The output of the program …