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

n

numbers is given, where

n

is an even number. The maximum as well as the minimum of these

n

numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

w

be the minimum weight among all edge weights in an undirected connected graph. Let

e

be a specific edge of weight

w

. Which of the following is FALSE?

\text{time complexity}

of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); }

In the following C function, let

n \geq m

. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?

In an unweighted, undirected connected graph, the shortest path from a node

S

to every other node is computed most efficiently, in terms of time complexity, by

Which of the following sorting algorithms has the lowest worse-case complexity?

Given two arrays of numbers

a_{1},...,a_{n}

b_{1},...,b_{n}

where each number is

0

1

, the fastest algorithm to find the largest span

(i, j)

a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}

or report that there is not such span,

Consider the following C-function in which

a[n]

b[m]

are two sorted integer arrays and

c[n+m]

be another integer array, void xyz(int a[], int b [], int c []){ int i,j,k; i=j=k=0; while ((i<n) && (j<m)) if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } Which of the following condition(s) hold(s) after the termination …

n

elements can be found in

O(n)

time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

Consider the following recurrence:

T(n)=2T\left ( \sqrt{n}\right )+1,

T(1)=1

Which one of the following is true?

X

can be represented by an array

x[n]

x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & \text{otherwise} \end{cases}

Consider the following algorithm in which

x

y

z

are Boolean arrays of size

n

: algorithm zzz(x[], y[], z[]) { int i; for(i=0; i<n; ++i) z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] …

T

be a depth first search tree in an undirected graph

G

u

ν

are leaves of this tree

T

. The degrees of both

u

ν

G

2

. which one of the following statements is true?

Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

An element in an array

X

is called a leader if it is greater than all elements to the right of it in

X

. The best algorithm to find all leaders in an array

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

Consider the following C-program fragment in which

i

j

n

are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let

val(j)

denote the value stored in the variable

j

after termination of the for loop. Which one of the following is true?

Which one of the following in place sorting algorithms needs the minimum number of swaps?

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Consider a weighted complete graph

G

on the vertex set

\{v_1,v_2,.....v_n\}

such that the weight of the edge

(v_i, v_j)

2|i-j|

. The weight of a minimum spanning tree of

G

9

T_1, T_2, \dots, T_9

. The execution of each task requires one unit of time. We can execute one task at a time. Each task

T_i

P_i

d_i

P_i

is earned if the task is completed before the end of the

d_i^{th}

unit of time. …