Previous Year Questions

Q1 MCQ GATE CS Medium 1 Mark 2026 Shift-1

ALGORITHM → RECURRENCE RELATIONS

Consider the following recurrence relations:
For all $n>1$
$T_{1}(n)=4T_{1}(\frac{n}{2})+T_{2}(n)$
$T_{2}(n)=5T_{2}(\frac{n}{4})+\Theta(log_{2}n)$
Assume that for all $n\le1$, $T_{1}(n)=1$ and $T_{2}(n)=1$.
Which one of the following options is correct?

Choose One:

A) $T_{1}(n)=\Theta(n^{2})$

B) $T_{1}(n)=\Theta(n^{2}log_{2}n)$

C) $T_{1}(n)=\Theta(n^{log_{4}5})$

D) $T_{1}(n)=\Theta(n^{log_{4}5}log_{2}n)$

Q2 MSQ GATE CS Easy 2 Marks 2026 Shift-1

ALGORITHM → GRAPH TRAVERSAL

An undirected, unweighted, simple graph $G(V,E)$ is said to be 2-colorable if there exists a function $c:V\rightarrow\{0,1\}$ such that for every $(u,v)\in E$, $c(u)\ne c(v)$. Which of the following statements about 2-colorable graphs is/are true?

Choose All Applicable:

A) If G is 2-colorable, then G may contain cycles of odd length

B) If G is 2-colorable, then G may contain cycles of even length

C) An optimal algorithm for testing whether G is 2-colorable runs in time $\Theta(|V|+|E|)$ if G is represented as an adjacency list

D) An optimal algorithm for testing whether G is 2-colorable runs in time $\Theta(|E|log|V|)$, if G is represented as an adjacency list

Q3 MSQ GATE CS Medium 2 Marks 2026 Shift-1

ALGORITHM → GRAPH TRAVERSAL

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V,E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of the vertex $v\in V$.

Explore(G,v,t)
 mark v
 t = t + 1
 d[v] = t
 for each (v,w) in E
  if w is unmarked
   t = Explore(G,w,t)
  end if
 end for
 t = t + 1
 f[v] = t
 return t

DFS(G):
 unmark all v in V
 t = 0
 for each v in V
  if v is unmarked
   t = Explore(G,v,t)
  end if
 end for

Suppose that the input directed graph $G(V,E)$ is a directed acyclic graph (DAG). For an edge $(u,v)\in E$, which of the following options will NEVER be correct?

Choose All Applicable:

A) $d[u]<d[v]<f[v]<f[u]$

B) $d[v]<d[u]<f[u]<f[v]$

C) $d[v]<f[v]<d[u]<f[u]$

D) $d[u]<d[v]<f[u]<f[v]$

Q4 MCQ GATE CS Medium 2 Marks 2026 Shift-1

ALGORITHM → SHORTEST PATH

Let $G(V,E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.
Let $s\in V$ be a vertex in G. For every $u\in V$ and for every $k\ge0$ let $d_{k}(u)$ denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then $d_{k}(u)=\infty.$
Consider the statements:
S1: For every $k\ge0$ and $u\in V$, $d_{k+1}(u)\le d_{k}(u)$.
S2: For every $(u,v)\in E$, if $(u,v)$ is part of a shortest path (in terms of weight) from s to v, then for every $k\ge0$, $d_{k}(u)\le d_{k}(v)$.
Which one of the following options is correct?

Choose One:

A) Only S1 is true

B) Only S2 is true

C) Both S1 and S2 are true

D) Neither S1 nor S2 is true

Q5 MSQ GATE CS Medium 2 Marks 2026 Shift-1

ALGORITHM → MINIMUM SPANNING TREE

Let $G(V,E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G~is/are$ true?

Choose All Applicable:

A) In every cycle C of G, the edge with the largest weight in C is not in any MST

B) In every cycle C of G, the edge with the smallest weight in C is in every MST

C) For every vertex $v\in V$, the edge with the largest weight incident on v is not in any MST

D) For every vertex $v\in V$, the edge with the smallest weight incident on v is in every MST

PYQBOOK

Filter Questions

Consider the following recurrence relations:
For all $n>1$
$T_{1}(n)=4T_{1}(\frac{n}{2})+T_{2}(n)$
$T_{2}(n)=5T_{2}(\frac{n}{4})+\Theta(log_{2}n)$
Assume that for all $n\le1$, $T_{1}(n)=1$ and $T_{2}(n)=1$.
Which one of the following options is correct?

Choose One:

An undirected, unweighted, simple graph $G(V,E)$ is said to be 2-colorable if there exists a function $c:V\rightarrow\{0,1\}$ such that for every $(u,v)\in E$, $c(u)\ne c(v)$. Which of the following statements about 2-colorable graphs is/are true?

Choose All Applicable:

Choose All Applicable:

Choose One:

Let $G(V,E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G~is/are$ true?

Choose All Applicable:

PYQBOOK

Filter Questions

Consider the following recurrence relations:For all $n>1$$T_{1}(n)=4T_{1}(\frac{n}{2})+T_{2}(n)$$T_{2}(n)=5T_{2}(\frac{n}{4})+\Theta(log_{2}n)$Assume that for all $n\le1$, $T_{1}(n)=1$ and $T_{2}(n)=1$.Which one of the following options is correct?

Choose One:

An undirected, unweighted, simple graph $G(V,E)$ is said to be 2-colorable if there exists a function $c:V\rightarrow\{0,1\}$ such that for every $(u,v)\in E$, $c(u)\ne c(v)$. Which of the following statements about 2-colorable graphs is/are true?

Choose All Applicable:

Choose All Applicable:

Choose One:

Let $G(V,E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G~is/are$ true?

Choose All Applicable:

Consider the following recurrence relations:
For all $n>1$
$T_{1}(n)=4T_{1}(\frac{n}{2})+T_{2}(n)$
$T_{2}(n)=5T_{2}(\frac{n}{4})+\Theta(log_{2}n)$
Assume that for all $n\le1$, $T_{1}(n)=1$ and $T_{2}(n)=1$.
Which one of the following options is correct?