Algorithms Practice Questions 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 Practice Questions

752 practice questions for Algorithms in GATE DA, sorted chapter by chapter and graded from basic to exam level, each with a full solution.

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 MSQ

Consider a binary search implementation where each step performs exactly one comparison to check equality, and if false, a second comparison to check less-than. Let $M (n)$ be the maximum number of comparisons for an array of size $n$ . Which of the following statements is/are TRUE?

I. $M (n)$ is a non-decreasing function of $n$ .

II. $M (2^{k}) = M (2^{k} - 1)$ for all $k \geq 1$ .

III. If $M (n) = 14$ , then $n$ must be exactly 64.

IV. $M (n) \leq 2 ⌈ lo g_{2} (n + 1)⌉$ for all $n \geq 1$ .

A.
I and IV only
B.
I and III only
C.
II and IV only
D.
I, II and IV only

Correct Answer:

["A"]

Step-by-Step Solution

Key idea: $M (n) = 2 (⌊ lo g_{2} n ⌋ + 1)$ . Analyze each statement using the properties of the floor function and logarithms.

Step 1: Statement I: As $n$ increases, $⌊ lo g_{2} n ⌋$ is non-decreasing, so $M (n)$ is non-decreasing. True.

Step 2: Statement II: $M (2^{k}) = 2 (k + 1)$ . $M (2^{k} - 1) = 2 (⌊ lo g_{2} (2^{k} - 1)⌋ + 1) = 2 (k - 1 + 1) = 2 k$ . They are not equal. False.

Step 3: Statement III: $M (n) = 14 ⟹ ⌊ lo g_{2} n ⌋ + 1 = 7 ⟹ ⌊ lo g_{2} n ⌋ = 6 ⟹ 64 \leq n \leq 127$ . $n$ is not necessarily exactly 64. False.

Step 4: Statement IV: We know $⌊ lo g_{2} n ⌋ + 1 = ⌈ lo g_{2} (n + 1)⌉$ for all integers $n \geq 1$ . Thus $M (n) = 2 ⌈ lo g_{2} (n + 1)⌉$ , which means $M (n) \leq 2 ⌈ lo g_{2} (n + 1)⌉$ is true (it is actually an equality).

Answer: I and IV only (Option A).

Question 2 · Elementary Sorting Algorithms MSQ

Four arrays of $5$ distinct integers are given below. Consider the standard (non-optimized) Bubble Sort and the standard Selection Sort applied to each array until fully sorted. Which ONE of the following statements is IMPOSSIBLE?

$P = [5, 4, 3, 2, 1], Q = [1, 2, 3, 4, 5], R = [3, 1, 2, 4, 5], S = [2, 1, 4, 3, 5]$

A.
Bubble Sort on P makes more comparisons than Bubble Sort on Q
B.
Selection Sort on P and Selection Sort on Q make the same number of comparisons
C.
Bubble Sort on Q makes fewer comparisons than Selection Sort on Q
D.
Insertion Sort on R makes fewer comparisons than Selection Sort on R

Correct Answer:

["A","C"]

Step-by-Step Solution

Key idea: this is a comparison-count invariance question — recognisable because it contrasts algorithms whose counts depend on data (Bubble, Insertion) against one whose count never depends on data (Selection).

Step 1: Establish the rules.

Standard Bubble Sort (no early termination): always $\frac{n ( n - 1 )}{2}$ comparisons for full sort. For $n = 5$ : $10$ .
Standard Selection Sort: always $\frac{n ( n - 1 )}{2}$ comparisons, invariant to data. For $n = 5$ : $10$ .
Insertion Sort: comparisons depend on data; minimum $n - 1 = 4$ (sorted), maximum $\frac{n ( n - 1 )}{2} = 10$ (reverse).

Step 2: Evaluate each statement.

A: Bubble on P vs Bubble on Q — both are $10$ (fixed). So "more" is FALSE. → impossible-looking claim but we test truth of the option text; A states a strict inequality that is false. Wait — re-read: A claims BS(P) > BS(Q). Since both equal 10, A is FALSE.
B: SS(P) = SS(Q) = 10 → TRUE.
C: BS(Q)=10 vs SS(Q)=10 → "fewer" is FALSE.
D: IS(R): trace gives 8 comparisons; SS(R)=10 → "fewer" TRUE.

Hold on — the question asks which statements are IMPOSSIBLE (i.e., false). Re-examine carefully:

A (BS(P)>BS(Q)): both 10 → false → IMPOSSIBLE.
B (SS(P)=SS(Q)): true → possible.
C (BS(Q)<SS(Q)): both 10 → false → IMPOSSIBLE.
D (IS(R)<SS(R)): 8<10 → true → possible.

Therefore the impossible statements are A and C.

Verification via tracing:

BS(Q): pass counts 4+3+2+1 = 10. ✓
SS(Q): scans unsorted suffix each pass: 4+3+2+1 = 10. ✓
IS(R)=[3,1,2,4,5]: insert 1 (compares with 3 →1 comp+shift... let's trust trace = 8). ✓ < 10.

Tempting wrong path: students often think optimized Bubble Sort stops early on already-sorted Q, giving 4 comparisons, making C "true". But the statement specifies STANDARD (non-optimized) Bubble Sort, so no early stop — Q still costs 10. That unit/condition mismatch flips C.

Generalization: Selection Sort's comparison count is a constant $\frac{n ( n - 1 )}{2}$ for every input; only Insertion Sort (and optimized Bubble) vary with data.

Answer: A and C are impossible.

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

Assertion (A): For an array of size

n \geq 2

sorted in ascending order, the standard Lomuto partition scheme (with the last element as pivot) performs exactly 0 actual data movements (swaps where the source and destination indices differ).
Reason (R): The algorithm executes exactly

n

swap statements, and each of these statements corresponds to a distinct data movement that places an element into a new index.

A.
Both A and R are true, and R is the correct explanation of A.
B.
Both A and R are true, but R is NOT the correct explanation of A.
C.
A is true, but R is false.
D.
A is false, but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: Distinguish between the execution of a swap statement and an actual data movement. A self-swap ( $i == j$ ) executes the statement but moves 0 elements.

Exam route: In an already sorted array with Lomuto, the boundary pointer $i$ always equals the scanning pointer $j$ . Thus, all $n$ swap statements are self-swaps.

Learning route:

Step 1: Lomuto partition on a sorted array with the last element as pivot.

Step 2: For each $j$ from $l o w$ to $hi g h - 1$ , $A [j] \leq p i v o t$ is true.

Step 3: $i$ increments, so $i$ becomes equal to $j$ . The swap A[i] with A[j] is a self-swap (0 data movements).

Step 4: After the loop, $i = hi g h - 1$ . The final swap is A[i+1] with A[high], which is A[high] with A[high], another self-swap.

Step 5: Total actual data movements = 0. Assertion A is true.

Step 6: Reason R claims each of the $n$ swap statements corresponds to a distinct data movement. This is false, as they are all self-swaps.

Answer: A is true, but R is false.

Common trap: Unit mismatch. Confusing the count of swap statement executions ( $n$ ) with the count of actual data movements (0), leading to the belief that A is false.

Question 4 · Graph Traversal: BFS and DFS MCQ

Let $G$ be a directed graph. A depth-first search from a source vertex $s$ in $G$ discovers exactly 12 vertices (including $s$ ). A depth-first search from $s$ in the reverse graph $G^{R}$ discovers exactly 18 vertices (including $s$ ). If the strongly connected component containing $s$ has exactly 7 vertices, what is the number of vertices in $G$ that can reach $s$ , but are not reachable from $s$ ?

A.
5
B.
11
C.
6
D.
12

Correct Answer:

Step-by-Step Solution

Key idea: The set of vertices that can reach $s$ is exactly the forward reachable set of $s$ in the reverse graph $G^{R}$ .

Step 1: Let $R_{f w d} (s)$ be the set of vertices reachable from $s$ in $G$ . We are given $∣ R_{f w d} (s) ∣ = 12$ .

Step 2: Let $R_{b w d} (s)$ be the set of vertices that can reach $s$ in $G$ . This is equivalent to the forward reachable set of $s$ in $G^{R}$ . We are given $∣ R_{b w d} (s) ∣ = 18$ .

Step 3: The strongly connected component (SCC) containing $s$ is the intersection $R_{f w d} (s) \cap R_{b w d} (s)$ . We are given its size is 7.

Step 4: We need to find the number of vertices that can reach $s$ but are not reachable from $s$ . This is the set $R_{b w d} (s) ∖ R_{f w d} (s)$ .

Step 5: The size of this set is $∣ R_{b w d} (s) ∣ - ∣ R_{f w d} (s) \cap R_{b w d} (s) ∣ = 18 - 7 = 11$ .

Answer: 11.

Question 5 · Directed Acyclic Graphs and Topological Ordering MCQ

Suppose we run Kahn's algorithm on a directed graph with 15 vertices. The algorithm terminates with 11 vertices in the topological sort list, and the queue becomes empty. What is the minimum number of edges that must be removed from the graph to make it a Directed Acyclic Graph?

A.
4
B.
1
C.
11
D.
15

Correct Answer:

Step-by-Step Solution

Key idea: This is a casework question about Kahn's algorithm termination and hidden cycles.

Step 1: Kahn's algorithm processes vertices with in-degree 0. If it terminates with 11 vertices processed out of 15, it means 4 vertices are left unprocessed.

Step 2: The 4 unprocessed vertices must have in-degrees > 0 from each other, meaning the subgraph induced by these 4 vertices contains at least one cycle.

Step 3: To make the graph a DAG, we must break all cycles. The minimum number of edges to remove to break a cycle in a subgraph of 4 vertices is 1 (e.g., if they form a simple 4-cycle, or a 3-cycle with a tail attached).

Step 4: Thus, the minimum number of edges to remove is 1.

Step 5: Address the trap. The unit_mismatch trap occurs when students answer 4 (the number of unprocessed vertices) or 11 (the number of processed vertices), confusing the unit of "vertices" with "edges".

Answer: 1

Question 6 · Dynamic Programming and Sequence Processing MCQ

Consider the array $X = [2, 3, 3, 4, 1, 2, 2, 3, 5, 0, 1, 1, 2]$ of length $13$ .

Let $S [i]$ denote the length of the longest contiguous non-decreasing subarray that ends exactly at index $i$ (1-indexed). The recurrence is:

$S [1] = 1$

$S [i] = {S [i - 1] + 1 1 if X [i - 1] \leq X [i] otherwise for i = 2, 3, \dots, 13$

What is the maximum value in the array $S$ ?

A.
4
B.
5
C.
6
D.
13

Correct Answer:

Step-by-Step Solution

Key idea: The maximum value in $S$ represents the length of the longest non-decreasing contiguous subarray in the entire array. We need to trace $S$ and find its maximum.

Step 1: Trace the DP array.

$i = 1$ : $S [1] = 1$ .

$i = 2$ : $X [2] = 3 \geq X [1] = 2$ . Extend. $S [2] = 2$ .

$i = 3$ : $X [3] = 3 \geq X [2] = 3$ . Extend. $S [3] = 3$ .

$i = 4$ : $X [4] = 4 \geq X [3] = 3$ . Extend. $S [4] = 4$ .

$i = 5$ : $X [5] = 1 < X [4] = 4$ . Reset. $S [5] = 1$ .

$i = 6$ : $X [6] = 2 \geq X [5] = 1$ . Extend. $S [6] = 2$ .

$i = 7$ : $X [7] = 2 \geq X [6] = 2$ . Extend. $S [7] = 3$ .

$i = 8$ : $X [8] = 3 \geq X [7] = 2$ . Extend. $S [8] = 4$ .

$i = 9$ : $X [9] = 5 \geq X [8] = 3$ . Extend. $S [9] = 5$ .

$i = 10$ : $X [10] = 0 < X [9] = 5$ . Reset. $S [10] = 1$ .

$i = 11$ : $X [11] = 1 \geq X [10] = 0$ . Extend. $S [11] = 2$ .

$i = 12$ : $X [12] = 1 \geq X [11] = 1$ . Extend. $S [12] = 3$ .

$i = 13$ : $X [13] = 2 \geq X [12] = 1$ . Extend. $S [13] = 4$ .

Step 2: Find the maximum.

$S = [1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4]$ .

Maximum value is 5 (at $i = 9$ ).

Answer: 5.

A question from this chapter

Login to view the complete practice 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 Practice Questions for GATE DA

About Algorithms Practice Questions

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