Algorithms Previous Year Questions
Previous year GATE questions on sorting and searching algorithms reveal consistent patterns that you can exploit in your preparation. This section breaks d...
GATE PYQ Analysis: Sorting and Searching Questions
Previous year GATE questions on sorting and searching algorithms reveal consistent patterns that you can exploit in your preparation. This section breaks down those patterns and provides representative examples with full solution approaches.
Pattern 1: number of comparisons. GATE regularly asks how many comparisons a specific algorithm makes on a specific input. For binary search on a sorted array of n elements, the maximum number of comparisons is floor(log2(n)) + 1. For an array of 15 elements, this is 4 comparisons. The minimum is 1 (if the element is at the middle position on the first comparison).
Pattern 2: state of array after k passes. Questions of the form "what does the array look like after 2 passes of bubble sort?" require you to simulate the algorithm. Example: given [5, 1, 4, 2, 8], after pass 1 of bubble sort: compare 5 and 1 (swap), compare 5 and 4 (swap), compare 5 and 2 (swap), compare 5 and 8 (no swap). Array: [1, 4, 2, 5, 8]. After pass 2: compare 1 and 4 (no swap), compare 4 and 2 (swap), compare 4 and 5 (no swap). Array: [1, 2, 4, 5, 8]. The largest element is in its final position after pass 1; the second largest after pass 2.
Pattern 3: worst-case input. Which input causes the most comparisons for a given algorithm? For quick sort with the first element as pivot, a sorted or reverse-sorted array causes O(n squared) comparisons. For insertion sort, a reverse-sorted array causes the maximum number of inversions: n(n-1)/2 comparisons and swaps.
Pattern 4: stability. GATE directly asks whether sorting algorithms are stable. Stable: bubble sort, insertion sort, merge sort, counting sort, radix sort. Not stable (in standard implementations): selection sort, quick sort, heap sort.
Pattern 5: lower bounds. GATE 2014 asked: "What is the minimum number of comparisons needed to find the minimum and maximum of n numbers?" The answer is 3(n-1)/2 for odd n and 3n/2 - 2 for even n, achieved by the tournament algorithm that compares pairs first. Proving this lower bound requires an adversary argument, which GATE has occasionally tested at the conceptual level.
Approach for unseen PYQs: identify the pattern, apply the known formula or simulation technique, and double-check with a small example before writing the final answer.
GATE PYQs on Graph Algorithms and Dynamic Programming
Graph algorithm and dynamic programming questions in GATE carry the highest proportion of 2-mark questions in the DAA section. Understanding the year-wise distribution helps you prioritise: graph algorithms (shortest paths, MST, traversals) appear in almost every GATE paper, while DP questions (LCS, matrix chain, knapsack) appear in roughly two out of three papers.
Graph algorithm PYQ patterns:
Pattern 1: Dijkstra trace. Given a weighted graph, apply Dijkstra's algorithm and report the order in which vertices are added to the settled set or the final distance array. The key is to correctly update distances when a shorter path is found through the newly settled vertex. GATE 2018 asked for the order of vertex extraction from the priority queue in Dijkstra's algorithm on a specific graph.
Pattern 2: MST weight or edge count. Given a graph with specific edge weights, find the total weight of the MST. Use Kruskal's algorithm: sort edges by weight and add them if they do not form a cycle. The MST of a connected graph with n vertices has exactly n-1 edges.
Pattern 3: topological sort validity. Given a directed graph, GATE may ask how many valid topological orderings exist or whether a specific ordering is valid. An ordering is valid if for every edge (u, v), u appears before v. The number of topological orderings can be computed by counting the orderings at each step where multiple vertices have in-degree zero.
DP PYQ patterns:
Pattern 1: LCS length. GATE 2012 asked for the LCS length of "ABCBDAB" and "BDCABA". Build the DP table entry by entry. The answer is 4.
Pattern 2: number of distinct optimal solutions. GATE sometimes asks not just the optimal value but the number of distinct solutions achieving that value, requiring you to trace back through the DP table and count paths.
Pattern 3: matrix chain multiplication cost. Given matrix dimensions, find the minimum number of scalar multiplications. Remember that multiplying an m by k matrix with a k by n matrix costs m times k times n multiplications.
Pattern 4: shortest path counting. How many shortest paths exist between two vertices in a graph? This can be computed by a DP on the shortest-path DAG: the number of paths to vertex v equals the sum of paths to all predecessors u such that dist(u) + w(u,v) equals dist(v).
Rare but High-Value GATE Questions and Final Preparation Tips
Some GATE algorithm questions are rare but worth studying because they carry 2 marks and require precise knowledge that most candidates lack. Scoring on these questions is a significant differentiator.
Amortised analysis questions: GATE has asked for the amortised cost of operations in data structures like the stack with multipop, the incrementing binary counter, and the dynamic table. For the incrementing binary counter, each increment flips the lowest 0 bit to 1 and all higher 1 bits to 0. The amortised cost per increment is O(1), even though individual increments can flip up to log n bits, because each bit is flipped from 1 to 0 at most as many times as it is flipped from 0 to 1.
String matching questions: KMP algorithm preprocessing. Given a pattern, compute the failure function (also called the partial match table or lps array). For the pattern "ABABC", the lps array is [0, 0, 1, 2, 0]. GATE may ask you to compute the lps array and determine the number of character comparisons made during matching on a specific text.
Randomised algorithms: GATE occasionally asks about randomised quick sort, where the pivot is chosen uniformly at random. The expected number of comparisons is O(n log n) in expectation. Understanding why: the expected number of comparisons between elements i and j (i less than j in sorted order) is 2 / (j - i + 1), and summing over all pairs gives O(n log n).
Flow network questions: maximum flow via Ford-Fulkerson. Given a flow network with source and sink, find the maximum flow. The max-flow min-cut theorem states that the maximum flow equals the minimum cut capacity. GATE has asked you to identify the minimum cut and compute its capacity.
Final preparation checklist for algorithms: (1) solve all GATE algorithm PYQs from 2005 to the most recent paper, (2) memorise Master Theorem cases and key algorithm complexities, (3) practise tracing Dijkstra, Prim, Kruskal, BFS, DFS, and topological sort on at least 5 different graphs each, (4) fill DP tables for LCS, edit distance, and matrix chain multiplication by hand at least 3 times each, (5) write out all NP-complete problems you know and the standard reductions between them.
On exam day, read algorithm questions carefully. The difference between "at most" and "exactly" or "maximum" and "minimum" changes the answer entirely. Underline quantifiers as you read. If you must guess, eliminate impossible answers using complexity bounds. A complexity of O(n) for a problem that provably requires Omega(n log n) comparisons can be immediately discarded.