GATE 2012 Algorithm Questions: Topic Map and Worked PYQs

Turn the five currently tagged GATE 2012 Algorithm items into a revision plan, with worked concepts and the official Code A outcomes kept separate.

KnowledgeGate Team

Exam prep & CS education

Updated 12 Nov 20265 min read
GATE 2012 Algorithm Questions: Topic Map and Worked PYQs

Finished the paper but unsure what to revise? Start with the five GATE 2012 Algorithm questions in the official CS-A paper and key. Their recurrences, cost models, MST edge case and Dijkstra tie trace form a bounded diagnostic, while the Code A key preserves two Marks to All outcomes.

GATE 2012 Algorithm PYQs: scope and official answer-key check

The completed paper and Code A key are in the IIT Kanpur GATE archive.

Question

Focus

Official Code A key

GATE CS exam hub (question link unavailable)

Towers of Hanoi recurrence

D

GATE CS exam hub (question link unavailable)

Average versus worst-case running time

C

GATE CS exam hub (question link unavailable)

Squared edge weights and MST

Marks to All

GATE CS exam hub (question link unavailable)

Merge sort on length-n strings

Marks to All

GATE CS exam hub (question link unavailable)

Dijkstra with equal shortest paths

D

Use the table as a diagnostic across recurrence, asymptotic analysis, spanning trees, sorting and shortest paths. The official paper remains the source for exact wording and numbering. For Q29 and Q39, concept calculation and the Code A award remain separate.

GATE 2012 Algorithm topic map: five questions, five reasoning skills

Question

Topic

Reasoning operation

Q16

Recurrence and base case

Model a recursive process

Q18

Average and worst case

Apply the definition

Q29

MST under transformed weights

Test a universal claim and edge cases

Q39

Merge sort with string keys

Combine comparison count and comparison cost

Q40

Dijkstra with ties

Trace distances and predecessors

A historical paper with one question per topic cannot support a percentage prediction. KnowledgeGate has over 1,200 Algorithm questions available for practice, but that count does not establish official frequency or weightage. Use GATE CS Exam Preparation for broader preparation.

GATE 2012 recurrence and asymptotic questions: work Q16 and Q18

For Q16, move n-1 discs away, move the largest once, then move n-1 back:

T(n) = 2T(n-1) + 1, with T(0) = 0.

For n = 4, T(1) = 1, T(2) = 3, T(3) = 7, and T(4) = 15, matching 2^4 - 1 = 15. Code A gives D. The traps are reducing to n/2 or charging n for the middle move.

For Q18, each runtime in an average is at most the maximum. With [2, 2, 2, 10], A = 16/4 = 4 and W = 10. Thus A(n) <= W(n) and A(n) = O(W(n)), Code A option C. It need not be o(W(n)), since average and worst cases can share an order.

GATE 2012 MST question: preserved order is not preserved total

Squaring is strictly increasing on positive weights: it preserves every strict comparison and every tie, so the collection of possible MST edge sets is unchanged. T and T' can still name different trees when a graph has multiple MSTs and two runs break ties differently. The total is a separate issue: t = sum(w_i) gives t^2 = sum(w_i^2) + 2 sum(i<j)(w_i w_j). A square of a sum is not a sum of squares.

For AB = 2, BC = 3, and AC = 5, the MST selects AB and BC, so t = 2 + 3 = 5. Squared weights are 4, 9 and 25. The same edges win, but t' = 4 + 9 = 13 < t^2 = 25.

A one-edge graph of weight 3 gives t = 3 and t' = 9 = t^2, so the strict inequality in option B is not universal. The triangle already defeats options A and C because its same MST has t' = 13 rather than t^2 = 25. No listed statement holds for every valid graph, so the conceptual answer is D. The official Code A key nevertheless awards Marks to All for Q29.

GATE 2012 merge-sort question: count character work too

Merge-sort cost trace multiplies 17 string comparisons by 8 character inspections to show O(n^2 log n).

Q39 hides cost inside comparisons. Merge sort uses O(n log n) comparisons, while two length-n strings may require O(n) character inspections. Multiplication gives O(n^2 log n), corresponding to option B in the answer choices.

For 8 strings of length 8, merge sort needs at most 8 log2(8) - 8 + 1 = 17 string comparisons in the worst case. If every comparison inspects all 8 characters, that gives at most 17 x 8 = 136 character inspections. The exact count strengthens the same O(n^2 log n) conclusion.

Code A says Marks to All for Q39. Keep O(n^2 log n) as the cost-composition lesson rather than treating it as an official award of only B. This Q39 trace isolates the cost of comparing length-n keys; Sorting Algorithms: Complexity and Comparison owns the broader comparison of stability, memory and standard complexity across sorting methods.

GATE 2012 Dijkstra question: trace equal-distance updates in Q40

From S, set B = 3, A = 4, and D = 7. B proposes 3 + 4 = 7 for D, so a strict-update rule keeps predecessor S on the tie. A sets C = 4 + 1 = 5; C sets E = 5 + 1 = 6, while C -> D = 8 loses.

E sets T = 6 + 4 = 10. D later proposes 7 + 3 = 10, so T keeps predecessor E. The chain is S -> A -> C -> E -> T, cost 4 + 1 + 1 + 4 = 10, Code A option D. The alternatives S -> D -> T = 7 + 3 = 10 and S -> B -> D -> T = 3 + 4 + 3 = 10 tie it.

Directed weighted graph for GATE 2012 Q40, highlighting shortest path S to A to C to E to T with cumulative distance 10.

Q40 isolates a strict-update tie on one official graph. For the wider family of representations, traversals and shortest-path methods, continue with Graph Algorithms: BFS, DFS and Shortest Paths.

GATE 2012 Algorithm lessons: a five-session revision loop

Run five sessions, one starting from each question. In every session, solve that item from a blank page, compare your result with the Code A outcome, then change one decisive condition and predict the new result. In the fifth session, leave time to retest one missed step from each earlier session.

  1. Rebuild the Hanoi recurrence and prove A(n) <= W(n).

  2. Recreate the n = 8 merge-sort cost calculation.

  3. Solve the 2, 3, 5 MST example and the single-edge countercase.

  4. Redraw Q40 and trace every distance and predecessor update.

  5. Solve all five again, tagging each miss as definition, cost model, quantifier, or state update.

No dynamic-programming item appears among the five questions. Use Dynamic Programming Explained: 0/1 Knapsack to move from recurrence recognition to state definitions and transitions.

The short version

The five GATE 2012 Algorithm items reward exact modelling more than memorised topic labels. The two Marks to All entries also show why sound concept work and the official award must remain separate. When these five traces are clean, the GATE Test Series is the structured next step for mixed practice.