Practice tests · GATE

GATE algorithms: 5 practice questions with solutions

By the PrepMatic team · Updated 9 Oct 2026 · 4 min read

Algorithms is a dedicated section in the GATE CS paper and part of "Programming, Data Structures and Algorithms" in DA. The questions ask you to do three things: find the time complexity of a recurrence or a loop, run a standard algorithm by hand on a small input, and pick the right design technique. The five original questions below practise all three.

What GATE tests in algorithms

The standard content is asymptotic analysis, searching and sorting, divide and conquer, greedy methods, dynamic programming and graph algorithms (traversals, minimum spanning trees, shortest paths). The CS and DA syllabi were revised for 2027, so check your paper's list on the official syllabus page. Expect "what is the complexity of this recurrence", "what does Dijkstra's algorithm output on this graph", "what is the optimal value for this knapsack or LCS instance" and "which problem does a greedy algorithm solve". NAT questions need exact numbers, so hand-simulation must be accurate. All five below are MCQ.

Practice questions

Question 1

The running time T(n) of an algorithm satisfies T(n) = 3T(n/2) + n², with T(1) = 1. Then T(n) is:

• A. Θ(n^(log₂ 3))
• B. Θ(n² log n)
• C. Θ(n³)
• D. Θ(n²)

Question 2

An undirected graph has vertices A, B, C, D, E and edges with weights: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 3. The length of the shortest path from A to E is:

• A. 10
• B. 11
• C. 12
• D. 13

Question 3

In a 0/1 knapsack problem the capacity is 10 and the items, given as (weight, value), are (3, 25), (4, 30), (5, 40) and (6, 45). The maximum total value that can be carried is:

• A. 65
• B. 70
• C. 75
• D. 80

Question 4

The minimum number of comparisons needed in the worst case to find both the largest and the smallest element of an unsorted array of 8 distinct elements is:

• A. 10
• B. 11
• C. 12
• D. 14

Question 5

What is the time complexity of the following code in terms of n? for (i = 1; i <= n; i = i * 2) for (j = 0; j < i; j++) count++;

• A. Θ(n log n)
• B. Θ(n²)
• C. Θ(log² n)
• D. Θ(n)

Answers and explanations

1. D. Apply the master theorem with a = 3, b = 2. Then n^(log₂ 3) is about n^1.585, which grows slower than f(n) = n². Since f(n) is polynomially larger and the regularity condition holds (3(n/2)² = 3n²/4 ≤ cn² with c = 3/4), T(n) = Θ(f(n)) = Θ(n²).
2. B. Run Dijkstra from A. dist(C) = 2. From C, dist(B) = 2 + 1 = 3. From B, dist(D) = 3 + 5 = 8 (the direct C–D edge would give 2 + 8 = 10). From D, dist(E) = 8 + 3 = 11, which beats the direct C–E route of 2 + 10 = 12. The path A, C, B, D, E has length 2 + 1 + 5 + 3 = 11.
3. C. Items 1 and 3 together (3 + 5 = 8, value 65) are what a greedy choice by value-to-weight ratio picks first, but nothing else fits. The best subset is items 2 and 4: weight 4 + 6 = 10, value 30 + 45 = 75. Dynamic programming over capacity confirms 75, and it shows why greedy fails for 0/1 knapsack.
4. A. Compare the elements in pairs: 4 comparisons for 8 elements. Compare the 4 winners among themselves to find the maximum (3 comparisons) and the 4 losers to find the minimum (3 comparisons). The total is 4 + 3 + 3 = 10, which equals ⌈3n/2⌉ − 2 for n = 8. The naive method needs 2(n − 1) = 14.
5. D. The inner loop runs i times, and i takes the values 1, 2, 4, …, up to n. The total is 1 + 2 + 4 + … + 2^k with 2^k about n, which is about 2n. This is Θ(n), not Θ(n log n): the loop counter doubles, so the work forms a geometric series dominated by its last term.

How to prepare algorithms

• Learn the master theorem cases and one fallback. The theorem covers T(n) = aT(n/b) + f(n); for anything else (T(n) = T(n − 1) + n, or unequal splits), expand the recursion or draw the tree.
• Know the common loop patterns. A doubling or halving counter gives log n; nested loops with a dependent inner bound need a sum; a geometric sum is dominated by its largest term (Question 5).
• Hand-simulate each classical algorithm once on a 5 to 7 node graph: BFS, DFS, Dijkstra, Prim, Kruskal, Bellman-Ford and Floyd-Warshall. Then practise on past-paper graphs until your tables are always right.
• For dynamic programming, set up the table first. Know LCS, edit distance, 0/1 knapsack, matrix chain multiplication and longest increasing subsequence with their recurrences.
• Memorise the bounds and the exceptions: quicksort O(n log n) average and O(n²) worst, the Ω(n log n) lower bound for comparison sorts, fractional knapsack is greedy but 0/1 is not, and Dijkstra needs non-negative weights.

Algorithms and data structures feed each other, so alternate between them. The GATE CSE preparation guide shows where this section sits in the CS plan, and theory of computation is a good next step.

Take the full topic test on PrepMatic

PrepMatic's topic tests run about 15 questions in 30 minutes, so you can practise hand-simulation under realistic time pressure. The free assessment shows your weakest subjects first.

← All practice tests