chapter

Algorithms PYQs for GATE CS

GATE CS Algorithms: 5 chapters, 47 previous year questions (100% of Algorithms), 10 practice questions and one solved question from each chapter.

A question from this chapter

Question 1

2026 Slot Set1 PYQ

Level 3: Exam Standard

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

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: 5 chapters, 47 previous year questions (100% of Algorithms), 10 practice questions and one solved question from each chapter.

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.

Algorithms Weightage in GATE CS

Algorithms accounts for 47 of 47 Algorithms previous year questions in our bank (100%), about 4.7 per paper across 10 papers.

Algorithms Chapter Matrix

Chapter	Topics	PYQs	Share of unit PYQs	Practice questions
Asymptotic Analysis and Recurrence Relations	Solving Recurrence Relations, Asymptotic Notation and Growth Comparison, Loop Complexity and Function Comparison	12	26%	0
Searching, Sorting, Selection and Hashing	Sorting Algorithms and Operation Counts, Binary and Bitonic Array Searching, Selection and Comparison Bounds, Linear-Time Array Property Verification, Universal Hashing and Adversarial Inputs	10	21%	10
Graph Traversal, Connectivity and Directed Graphs	Breadth-First Search Trees and Applications, Depth-First Search Edges and Timestamps, Connected Components and Articulation Points, Directed Graphs, Cycles and Strong Connectivity, Greedy Graph Coloring	10	21%	0
Minimum Spanning Trees and Shortest Paths	MST Cut-Cycle Properties and Uniqueness, Minimum Spanning Tree Construction and Counting, Shortest-Path Properties and Algorithms, Effects of Edge-Weight Transformations	10	21%	0
Dynamic Programming, Greedy Algorithms and Optimization	Longest Non-Decreasing Subsequences and Array Optimization, Rod Cutting Dynamic Programming, Huffman Coding and Prefix-Free Codes, Optimal Path Computation in Directed Acyclic Graphs, Dynamic Programming Table Evaluation	5	11%	0

One Solved Question from Each Algorithms Chapter

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

Consider the following recurrence relations:

For all

n > 1

T_{1} (n) = 4 T_{1} (\frac{n}{2}) + T_{2} (n)

T_{2} (n) = 5 T_{2} (\frac{n}{4}) + Θ (lo g_{2} n)

Assume that for all

n \leq 1

T_{1} (n) = 1

and

T_{2} (n) = 1

.

Which one of the following options is correct?

A.
$T_{1} (n) = Θ (n^{2})$
B.
$T_{1} (n) = Θ (n^{2} lo g_{2} n)$
C.
$T_{1} (n) = Θ (n^{l o g_{4} 5})$
D.
$T_{1} (n) = Θ (n^{l o g_{4} 5} lo g_{2} n)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a system of recurrence relations, recognizable because $T_{1} (n)$ depends on the solution of $T_{2} (n)$ .

Why this method applies: We must solve the recurrences sequentially, starting from the one that is self-contained ( $T_{2}$ ), find its asymptotic bound, and then substitute that bound into the other recurrence ( $T_{1}$ ).

Step 1: Solve $T_{2} (n) = 5 T_{2} (n /4) + Θ (lo g_{2} n)$ using the Master Theorem.

Step 2: Identify $a = 5, b = 4$ . The critical exponent is $lo g_{4} 5 \approx 1.16$ .

Step 3: Compare the driving function $f (n) = lo g_{2} n$ with $n^{l o g_{4} 5}$ . Since $lo g_{2} n$ grows strictly slower than any positive polynomial power of $n$ , $f (n) = O (n^{l o g_{4} 5 - ϵ})$ for some $ϵ > 0$ .

Step 4: By Case 1 of the Master Theorem, $T_{2} (n) = Θ (n^{l o g_{4} 5})$ .

Step 5: Substitute this into the first recurrence: $T_{1} (n) = 4 T_{1} (n /2) + Θ (n^{l o g_{4} 5})$ .

Step 6: Apply the Master Theorem to $T_{1} (n)$ . Here, $a = 4, b = 2$ . The critical exponent is $lo g_{2} 4 = 2$ .

Step 7: Compare the new driving function $f (n) = n^{l o g_{4} 5}$ with $n^{2}$ . Since $lo g_{4} 5 \approx 1.16 < 2$ , we have $f (n) = O (n^{2 - ϵ})$ for $ϵ \approx 0.84$ .

Step 8: By Case 1 of the Master Theorem again, the root dominates, so $T_{1} (n) = Θ (n^{l o g_{2} 4}) = Θ (n^{2})$ .

Answer: Option A is correct.

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

A question from this chapter

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Algorithms PYQs for GATE CS

About Algorithms Previous Year Questions (PYQs)

Algorithms Weightage in GATE CS

Algorithms Chapter Matrix

More from Algorithms

One Solved Question from Each Algorithms Chapter

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution