Algorithms PYQs for GATE DA

GATE DA Algorithms: 6 chapters, 14 previous year questions (45% of Programming, Data Structures and Algorithms), 752 practice questions and one solved question from each chapter.

About Algorithms Previous Year Questions (PYQs)

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

Algorithms Weightage in GATE DA

Algorithms accounts for 14 of 31 Programming, Data Structures and Algorithms previous year questions in our bank (45%), about 4.7 per paper across 3 papers.

Algorithms Chapter Matrix

Chapter	Topics	PYQs	Share of unit PYQs	Practice questions
Searching Algorithms and Binary Search	Binary Search Recurrence and Worst-Case Comparisons, Binary Search Preconditions and Data Representation	3	21%	157
Elementary Sorting Algorithms	Bubble, Insertion and Selection Sort Pass Analysis, Insertion Sort Swaps and Nearly Sorted Arrays	3	21%	160
Quicksort and Divide-and-Conquer Analysis	Quicksort Partitioning and Swap Count, Expected Recurrence Analysis of Randomized Quicksort	2	14%	118
Graph Traversal: BFS and DFS	Reachability in Directed Graph Traversals, DFS Discovery Order and Edge Classification, Graph Traversal on Given Diagrams	4	29%	210
Directed Acyclic Graphs and Topological Ordering	Topological Ordering of DAGs	1	7%	52
Dynamic Programming and Sequence Processing	Dynamic Programming for Consecutive Sequence Lengths	1	7%	55

One Solved Question from Each Algorithms Chapter

Question 1 · Searching Algorithms and Binary Search · 2026 NAT

Let A be a sorted array containing 1000 distinct integers. You perform a recursive binary search on A to find an element y. Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than y.
The maximum number of comparisons that may have to be performed if y is not an element of A is _______ . (Answer in integer)

Correct Answer:

10.00

Step-by-Step Solution

Insight: A 3-way comparison counts as exactly 1 comparison per step. The max comparisons is simply the depth of the recursion tree.

Exam route: Use the formula $⌊ lo g_{2} n ⌋ + 1$ . For $n = 1000$ , $⌊ 9.96 ⌋ + 1 = 10$ .

Learning route:

The problem specifies a 3-way comparison (equal, less, greater). This counts as 1 comparison per recursive step.

The maximum number of comparisons is the maximum depth of the recursion tree, which occurs when the element is not found or is at the deepest leaf.

The exact formula for the maximum depth (number of comparisons) is $⌊ lo g_{2} n ⌋ + 1$ .

Given $n = 1000$ :

$lo g_{2} 1000 \approx 9.965$ .

$⌊ 9.965 ⌋ = 9$ .

Total comparisons = $9 + 1 = 10$ .

If the problem had specified two separate checks (e.g., if A[mid] == y then else if A[mid] < y), the worst case would be 2 comparisons per step, yielding 20. But the 3-way comparison explicitly avoids this trap.

Question 2 · Elementary Sorting Algorithms · 2026 MSQ

Consider the problem of sorting the given array in ascending order:

P = [1, 2, 3, 5, 4]

Consider two sorting algorithms Bubble Sort (BS) and Insertion Sort (IS).

Let N1 be the total number of comparisons done by BS on the elements of P and N2 be the total number of comparisons done by IS on the elements of P.

Which of the following options is/are correct?

A.
N1 = 10, N2 = 4
B.
N1 > N2
C.
IS on P will perform only one swap
D.
Both BS and IS on P will make at least one unnecessary comparison (i.e., comparing elements that are already in correct order)

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Insight: This is a pass-analysis question recognisable because it asks for exact operation counts on a tiny concrete array. The pivot is that Bubble Sort (standard, no early termination) has a deterministic comparison count while Insertion Sort's count is data-dependent and must be traced element by element.

Exam route:

Compute N1 using the fixed formula: for $n = 5$ , standard Bubble Sort does $(n - 1) + (n - 2) + (n - 3) + (n - 4) = 4 + 3 + 2 + 1 = 10$ ... wait, that is only for a full sort. Let us recompute carefully: pass 1 does $n - 1 = 4$ , pass 2 does $n - 2 = 3$ , pass 3 does $2$ , pass 4 does $1$ . Total $= 4 + 3 + 2 + 1 = 10$ .
Trace Insertion Sort on $P = [1, 2, 3, 5, 4]$ :

key=2: compare with 1 (1 cmp), no shift.
key=3: compare with 2 (1 cmp), no shift.
key=5: compare with 3 (1 cmp), no shift.
key=4: compare with 5 (shift), compare with 3 (stop) → 2 cmp, 1 shift.
Total $N_{2} = 1 + 1 + 1 + 2 = 5$ , shifts $= 1$ .

Evaluate options: $N_{1} = 10, N_{2} = 5$ ; $N_{1} > N_{2}$ holds; IS does exactly 1 swap; BS in passes 2–4 compares already-sorted adjacent pairs (unnecessary), and IS compares 4 with 5 which are out of order but the comparison that stops at 3 (already in correct relative order with 4) is the boundary check — BS clearly makes unnecessary comparisons, so D holds.

Learning route:

Bubble Sort (standard, no flag) always performs exactly $\sum_{i = 1}^{n - 1} (n - i) = \frac{n ( n - 1 )}{2}$ comparisons regardless of input. For $n = 5$ , $N_{1} = 10$ .

Insertion Sort comparisons depend on how far each key travels. Tracing $P = [1, 2, 3, 5, 4]$ :

key=2 vs {1}: 1 comparison, 0 shifts.
key=3 vs {1,2}: 1 comparison, 0 shifts.
key=5 vs {1,2,3}: 1 comparison, 0 shifts.
key=4 vs {1,2,3,5}: compares with 5 (shift), then with 3 (stop) → 2 comparisons, 1 shift.

Total $N_{2} = 5$ , shifts = 1.

Option A claims $N_{1} = 10, N_{2} = 4$ — wrong because $N_{2} = 5$ , not 4.

Option B: $10 > 5$ — true.

Option C: IS performs exactly 1 swap/shift — true.

Option D: BS in passes 2, 3, 4 compares pairs already in correct order (e.g. 1 and 2 in pass 2); IS compares 4 with 5 which are out of order but the stop-comparison with 3 is against an element already in correct relative position — both algorithms make at least one such comparison. True.

Verification: re-running both algorithms on $P$ confirms $N_{1} = 10, N_{2} = 5$ , 1 IS shift, and unnecessary comparisons in both.

Answer: B, C, D.

Question 3 · Quicksort and Divide-and-Conquer Analysis · 2026 MCQ

Consider that the quick sort algorithm is used to sort an array of n distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.
Let

T (n)

denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.
Which of the following recurrence relations correctly represents

T (n)

in this scenario?

A.
$T (n) = T (1) + T (n - 1) + O (n)$
B.
$T (n) = T (\frac{n}{4}) + T (\frac{3 n}{4}) + O (n)$
C.
$T (n) = 2 T (\frac{n}{2}) + O (n)$
D.
$T (n) = \frac{1}{n} \sum_{k = 0}^{n - 1} [T (k) + T (n - k - 1)] + O (n)$

Correct Answer:

Step-by-Step Solution

Key idea: This is an expected recurrence analysis problem for Quicksort, recognizable by the phrases "expected time", "randomly ordered elements", and a fixed pivot position (first element).

Step 1: Understand the pivot selection dynamics.

Although the pivot is deterministically chosen as the first element of the subarray, the array itself is randomly ordered. This means the first element is equally likely to be the $1$ st, $2$ nd, ..., or $n$ -th smallest element in the subarray.

Step 2: Determine the subproblem sizes.

Let the rank of the chosen pivot be $k + 1$ (where $k$ ranges from $0$ to $n - 1$ ).

The left subarray will contain the $k$ elements smaller than the pivot.
The right subarray will contain the remaining $n - 1 - k$ elements larger than the pivot.

Step 3: Formulate the expected time recurrence.

Since each possible rank $k$ occurs with a uniform probability of $\frac{1}{n}$ , the expected time $T (n)$ is the average of the expected times of all possible splits, plus the $O (n)$ time required for the partitioning step itself.

Mathematically, this is expressed as:

$T (n) = \frac{1}{n} k = 0 \sum n - 1 [T (k) + T (n - k - 1)] + O (n)$

Step 4: Match with the given options.

This derived formula exactly matches the fourth option.

Answer: D

Question 4 · Graph Traversal: BFS and DFS · 2026 MCQ

Consider a directed graph

G = (V, E)

, where

V

is the finite set of vertices and

E

is the set of directed edges between the vertices.

G

may contain cycles but there is no self-loop. Further,

G

may not be strongly connected.

Let

G^{R}

be the graph obtained by reversing the directions of all the edges in

G

without changing the set of vertices.

Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex

v

of a graph visits only the reachable vertices from

v

in that graph.

Which of the following statements must always be true, regardless of the structure of

G

A.
If $u$ is a reachable vertex in the BFS of $G^{R}$ from $v$ , then $u$ is also a reachable vertex in the DFS of $G$ from $v$ .
B.
In $G^{R}$ , the BFS traversal from $v$ will visit exactly the same set of vertices as the DFS from $v$ in $G$ .
C.
The order of vertices visited in the BFS of $G^{R}$ from $v$ is the reverse of the order of vertices visited in the DFS of $G$ from $v$ .
D.
If $u$ is a reachable vertex in the DFS of $G$ from $v$ , then $v$ is also a reachable vertex in the BFS of $G^{R}$ from $u$ .

Correct Answer:

Step-by-Step Solution

Insight: BFS/DFS on $G^{R}$ from $v$ finds exactly the set of vertices that can reach $v$ in $G$ . BFS/DFS on $G$ from $v$ finds exactly the set of vertices reachable from $v$ in $G$ .

Exam route: Translate each option into reachability language in $G$ .

Learning route:

Let $R_{f w d} (v)$ = vertices reachable from $v$ in $G$ . This is what DFS/BFS on $G$ from $v$ returns.
Let $R_{b w d} (v)$ = vertices that can reach $v$ in $G$ . This is what DFS/BFS on $G^{R}$ from $v$ returns.
Option A: $u \in R_{b w d} (v) ⟹ u \in R_{f w d} (v)$ . False. Counter-example: $u \to v$ only. $u$ can reach $v$ but $v$ cannot reach $u$ .
Option B: $R_{b w d} (v) = R_{f w d} (v)$ . False. Same counter-example.
Option C: BFS order is reverse of DFS order. False. BFS is level-by-level, DFS is deep-first; no reason for reversal.
Option D: $u \in R_{f w d} (v)$ in $G ⟹ v \in R_{b w d} (u)$ in $G$ .

If $u$ is reachable from $v$ in $G$ , there is a path $v \to \dots \to u$ .

Reversing all edges gives $u \to \dots \to v$ in $G^{R}$ .

So $v$ is reachable from $u$ in $G^{R}$ . This is exactly $v \in R_{b w d} (u)$ in $G$ (which is computed by BFS on $G^{R}$ from $u$ ).

True.

Answer: D.

Question 5 · Directed Acyclic Graphs and Topological Ordering · 2024 MSQ

Consider the directed acyclic graph (DAG) below:

Which of the following is/are valid vertex orderings that can be obtained from a
topological sort of the DAG?

A.
P Q R S T U V
B.
P R Q V S U T
C.
P Q R S V U T
D.
P R Q S V T U

Correct Answer:

["B","D"]

Step-by-Step Solution

Insight: A topological sort is valid if and only if for every directed edge $u \to v$ , vertex $u$ appears before vertex $v$ in the linear ordering.

Exam route: Extract all directed edges from the graph diagram. Check each given option to see if it violates any of these precedence constraints. Eliminate options with violations.

Learning route:

Step 1: Identify the vertices and directed edges from the SVG diagram.

The edges are: $P \to Q$ , $R \to Q$ , $Q \to S$ , $Q \to V$ , $S \to U$ , and $V \to T$ .

Step 2: List the precedence constraints derived from these edges:

$P$ must appear before $Q$ .
$R$ must appear before $Q$ .
$Q$ must appear before $S$ and $V$ .
$S$ must appear before $U$ .
$V$ must appear before $T$ .

Step 3: Evaluate each option against these constraints.

Option A ("P Q R S T U V"): $Q$ appears before $R$ . This violates the constraint $R \to Q$ . Invalid.
Option B ("P R Q V S U T"): $P, R$ are before $Q$ ; $Q$ is before $V$ and $S$ ; $S$ is before $U$ ; $V$ is before $T$ . All constraints are satisfied. Valid.
Option C ("P Q R S V U T"): $Q$ appears before $R$ . This violates the constraint $R \to Q$ . Invalid.
Option D ("P R Q S V T U"): $P, R$ are before $Q$ ; $Q$ is before $S$ and $V$ ; $S$ is before $U$ ; $V$ is before $T$ . All constraints are satisfied. Valid.

Step 4: Conclude that options B and D are the valid topological orderings.

Question 6 · Dynamic Programming and Sequence Processing · 2024 MCQ

Consider the function computeS(X) whose pseudocode is given below:

computeS(X)

S [1] \leftarrow 1

for

i \leftarrow 2

l e n g t h (X)

S [i] \leftarrow 1

X [i - 1] \leq X [i]

S [i] \leftarrow S [i] + S [i - 1]

end if
end for
return S

Which ONE of the following values is returned by the function computeS(X)
for X = [6, 3, 5, 4, 10]?

A.
[1, 1, 2, 3, 4]
B.
[1, 1, 2, 3, 3]
C.
[1, 1, 2, 1, 2]
D.
[1, 1, 2, 1, 5]

Correct Answer:

Step-by-Step Solution

Insight: This is a consecutive sequence DP question where S[i] represents the length of the longest non-decreasing contiguous subarray ending at index i. The pseudocode implements the standard "extend or reset" pattern.

Exam route: Trace the pseudocode step by step for the given array X = [6, 3, 5, 4, 10].

Learning route:

i=1: S[1] = 1 (base case, single element is always valid).
i=2: X[1]=6, X[2]=3. Check 6 <= 3: false. So S[2] remains 1 (reset).
i=3: X[2]=3, X[3]=5. Check 3 <= 5: true. So S[3] = 1 + S[2] = 1 + 1 = 2 (extend).
i=4: X[3]=5, X[4]=4. Check 5 <= 4: false. So S[4] remains 1 (reset).
i=5: X[4]=4, X[5]=10. Check 4 <= 10: true. So S[5] = 1 + S[4] = 1 + 1 = 2 (extend).

Final array: S = [1, 1, 2, 1, 2].

Verification: The longest non-decreasing contiguous subarrays ending at each index are: [6] (length 1), [3] (length 1), [3, 5] (length 2), [4] (length 1), [4, 10] (length 2). This matches S = [1, 1, 2, 1, 2].

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 DA

About Algorithms Previous Year Questions (PYQs)

Algorithms Weightage in GATE DA

Algorithms Chapter Matrix

More from Programming, Data Structures and Algorithms

One Solved Question from Each Algorithms Chapter

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution