chapter

Algorithms PYQs for GATE CS

GATE CS Algorithms: 1 units and 5 chapters, weightage from 47 previous year questions across 10 papers, a study order by exam weight and 10 practice questions

A question from this chapter

Question 1

2026 Slot Set2 PYQ

Consider the following functions, where n is a positive integer. n^{1/3}, lo g (n), lo g (n!), 2^{l o g (n)} Which one of the following options lists the functions in increasing order of asymptotic growth rate? Note: Assume the base of log to be 2.

Question 2

2026 Slot Set2 PYQ

Level 3: Exam Standard

Consider an array A = [10, 7, 8, 19, 41, 35, 25, 31] . Suppose the merge sort algorithm is executed on array A to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations. A merge operation on sorted left array L and sorted right array R is said to be void if the output of the merge operation is the elements of array L followed by the elements of array R . The number of void merge operations among these 7 merge operations is __________. (answer in integer)

Question 3

2026 Slot Set1 PYQ

Level 3: Exam Standard

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 . D F S (G) : unmark all v \in V t \leftarrow 0 for each v \in V if v is unmarked t \leftarrow E x pl or e (G, v, t) end if end for E x pl or e (G, v, t) : mark v t \leftarrow t + 1 d [v] \leftarrow t for each (v, w) \in E if w is unmarked t \leftarrow E x pl or e (G, w, t) end if end for t \leftarrow t + 1 f [v] \leftarrow t return t 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?

Question 4

2026 Slot Set2 PYQ

Level 4: Challenger

Let G be a weighted directed acyclic graph with m edges and n vertices. Given G and a source vertex s in G, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from s to all vertices that are reachable from s in G ?

Question 5

2026 Slot Set2 PYQ

Consider a table T, where the elements T [i] [j], 0 \leq i, j \leq n, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows: T [0] [k] = T [k] [0] = 1 for k = 0, 1, 2, \dots, n T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1] for 1 \leq i, j \leq n Consider the following two algorithms to compute entries of T . Assume that for both the algorithms, for all 0 \leq i, j \leq n, T [i] [j] has been initialized to 1 . Algorithm B_{1} : For i = 1, 2, \dots, n For j = 1, 2, \dots, n T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1] Algorithm B_{2} : For s = 2, 3, \dots, 2 n For i = 1, 2, \dots, n For j = 1, 2, \dots, n If (i + j == s) T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1] Algorithm B_{k}, k \in {1, 2} is said to be correct if and only if it calculates the correct values of T [i] [j], for all 0 \leq i, j \leq n, (as per the recursive formulation) at the end of the execution of the algorithm B_{k} . Which one of the following statements is true?

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Algorithms PYQs for GATE CS

GATE CS Algorithms: 1 units and 5 chapters, weightage from 47 previous year questions across 10 papers, a study order by exam weight and 10 practice questions.

About Algorithms Previous Year Questions (PYQs)

47 previous year questions from Algorithms in GATE CS, grouped by chapter with the exam year, answer key and step-by-step solution for each.

GATE CS Algorithms Unit-wise Weightage from Past Papers

We counted every GATE CS Algorithms previous year question in our bank (47 questions from 10 papers) and grouped them by unit.

Unit	Chapters	PYQs	Share of section	Avg per paper
Algorithms	5	47	100%	4.7

Suggested Algorithms Study Order for GATE CS

Algorithms: 100% of past Algorithms questions, about 4.7 per paper.

Start where the marks are. Units at the top of this list have appeared most often in past GATE CS papers.

Units in GATE CS Algorithms

Algorithms Previous Year Questions (PYQs) (5 chapters)

All Algorithms chapters

One Solved Question from Each Algorithms Chapter

Question 1 · Asymptotic Analysis and Recurrence Relations · 2026_Set2 MCQ

Consider the following functions, where

n

is a positive integer.

n^{1/3}, lo g (n), lo g (n!), 2^{l o g (n)}

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

Note: Assume the base of log to be 2.

A.
$lo g (n), n^{1/3}, 2^{l o g (n)}, lo g (n!)$
B.
$n^{1/3}, lo g (n), lo g (n!), 2^{l o g (n)}$
C.
$lo g (n), n^{1/3}, lo g (n!), 2^{l o g (n)}$
D.
$2^{l o g (n)}, n^{1/3}, lo g (n), lo g (n!)$

Question 2 · Searching, Sorting, Selection and Hashing · 2026_Set2 NAT

Consider an array

A = [10, 7, 8, 19, 41, 35, 25, 31]

. Suppose the merge sort algorithm is executed on array

A

to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations.

A merge operation on sorted left array

L

and sorted right array

R

is said to be void if the output of the merge operation is the elements of array

L

followed by the elements of array

R

.

The number of void merge operations among these 7 merge operations is __________. (answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: This is a merge sort operation counting question, recognisable because it asks for the number of "void" merge operations on a specific array. A void merge occurs when the left subarray's maximum element is less than or equal to the right subarray's minimum element.

Step 1: Trace the merge sort tree for $A = [10, 7, 8, 19, 41, 35, 25, 31]$ .

Step 2: Level 3 (size 1 to 2):

Merge $[10]$ and $[7] \to [7, 10]$ . Not void ( $10 > 7$ ).
Merge $[8]$ and $[19] \to [8, 19]$ . Void ( $8 \leq 19$ ). (Count = 1)
Merge $[41]$ and $[35] \to [35, 41]$ . Not void ( $41 > 35$ ).
Merge $[25]$ and $[31] \to [25, 31]$ . Void ( $25 \leq 31$ ). (Count = 2)

Step 3: Level 2 (size 2 to 4):

Merge $[7, 10]$ and $[8, 19] \to [7, 8, 10, 19]$ . Not void ( $10 > 8$ ).
Merge $[35, 41]$ and $[25, 31] \to [25, 31, 35, 41]$ . Not void ( $41 > 25$ ).

Step 4: Level 1 (size 4 to 8):

Merge $[7, 8, 10, 19]$ and $[25, 31, 35, 41] \to [7, 8, 10, 19, 25, 31, 35, 41]$ . Void ( $19 \leq 25$ ). (Count = 3)

Step 5: Total void merges = 3.

Answer: 3

Question 3 · Graph Traversal, Connectivity and Directed Graphs · 2026_Set1 MSQ

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

D F S (G) :

unmark all

v \in V

t \leftarrow 0

for each

v \in V

v

is unmarked

t \leftarrow E x pl or e (G, v, t)

end if
end for

E x pl or e (G, v, t) :

mark

v

t \leftarrow t + 1

d [v] \leftarrow t

for each

(v, w) \in E

w

is unmarked

t \leftarrow E x pl or e (G, w, t)

    end if
  end for

t \leftarrow t + 1

f [v] \leftarrow t

return

t

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?

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]$

Correct Answer:

["B","D"]

Step-by-Step Solution

Key idea: This is a "DFS timestamp and DAG properties" question, recognisable because it asks which timestamp relationships are impossible for an edge in a Directed Acyclic Graph.

Step 1: Understand the Parenthesis Theorem.

For any two vertices $u$ and $v$ in a DFS traversal, their discovery/finish intervals $[d [u], f [u]]$ and $[d [v], f [v]]$ must be either completely disjoint or perfectly nested. They can never partially overlap.

Step 2: Evaluate Option D.

$d [u] < d [v] < f [u] < f [v]$ represents partially overlapping intervals. This violates the Parenthesis Theorem and is impossible in ANY DFS traversal, regardless of whether the graph is a DAG. Thus, Option D will NEVER be correct.

Step 3: Evaluate Option B.

$d [v] < d [u] < f [u] < f [v]$ represents perfectly nested intervals where $v$ is an ancestor of $u$ . This means the edge $(u, v)$ goes from a descendant to an ancestor, which is the definition of a back edge. A back edge implies the existence of a cycle. Since the input graph is a DAG (Directed Acyclic Graph), it cannot contain any cycles, and therefore cannot contain any back edges. Thus, Option B will NEVER be correct.

Step 4: Evaluate Options A and C.

Option A ( $d [u] < d [v] < f [v] < f [u]$ ) represents nested intervals where $u$ is an ancestor of $v$ . This corresponds to a tree edge or forward edge, which are perfectly valid in a DAG.

Option C ( $d [v] < f [v] < d [u] < f [u]$ ) represents disjoint intervals where $v$ is completely finished before $u$ is discovered. This corresponds to a cross edge, which is also valid in a DAG.

Answer: B, D

Question 4 · Minimum Spanning Trees and Shortest Paths · 2026_Set2 MCQ

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$ , which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from $s$ to all vertices that are reachable from $s$ in $G$ ?

A.
$Θ (m + n)$
B.
$Θ (m + n lo g (n))$
C.
$Θ (nm)$
D.
$Θ (n^{3})$

Correct Answer:

Step-by-Step Solution

Key idea: Shortest paths in a Directed Acyclic Graph (DAG) can be found in linear time using topological sorting.

Step 1: Recognize that the graph is a DAG. This is the crucial condition that allows a faster algorithm than Dijkstra's or Bellman-Ford.

Step 2: Perform a topological sort of the vertices. This takes $Θ (m + n)$ time using DFS or Kahn's algorithm.

Step 3: Initialize the distance to the source vertex $s$ as 0, and all other vertices as $\infty$ .

Step 4: Process each vertex $u$ in topological order. For each outgoing edge $(u, v)$ with weight $w$ , relax the edge: if $d i s t [v] > d i s t [u] + w$ , update $d i s t [v] = d i s t [u] + w$ .

Step 5: Since each vertex and each edge is processed exactly once in the topological order, the relaxation step takes $Θ (m + n)$ time.

Answer: $Θ (m + n)$

Question 5 · Dynamic Programming, Greedy Algorithms and Optimization · 2026_Set2 MCQ

Consider a table

T

, where the elements

T [i] [j]

0 \leq i, j \leq n

, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:

T [0] [k] = T [k] [0] = 1 for k = 0, 1, 2, \dots, n

T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1] for 1 \leq i, j \leq n

Consider the following two algorithms to compute entries of

T

. Assume that for both the algorithms, for all

0 \leq i, j \leq n

T [i] [j]

has been initialized to

1

.

Algorithm

B_{1}

: For

i = 1, 2, \dots, n

For

j = 1, 2, \dots, n

T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1]

Algorithm

B_{2}

: For

s = 2, 3, \dots, 2 n

For

i = 1, 2, \dots, n

For

j = 1, 2, \dots, n

(i + j == s)

T [i] [j] = 2 T [i - 1] [j] + 3 T [i] [j - 1]

Algorithm

B_{k}

k \in {1, 2}

is said to be correct if and only if it calculates the correct values of

T [i] [j]

, for all

0 \leq i, j \leq n

, (as per the recursive formulation) at the end of the execution of the algorithm

B_{k}

.

Which one of the following statements is true?

A.
Both algorithms $B_{1}$ and $B_{2}$ are correct
B.
Algorithm $B_{1}$ is correct, but algorithm $B_{2}$ is incorrect
C.
Algorithm $B_{2}$ is correct, but algorithm $B_{1}$ is incorrect
D.
Both algorithms $B_{1}$ and $B_{2}$ are incorrect