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

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 |
|---|---|---|
Towers of Hanoi recurrence | D | |
Average versus worst-case running time | C | |
Squared edge weights and MST | Marks to All | |
Merge sort on length-n strings | Marks to All | |
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

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.

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.
Rebuild the Hanoi recurrence and prove
A(n) <= W(n).Recreate the n = 8 merge-sort cost calculation.
Solve the 2, 3, 5 MST example and the single-edge countercase.
Redraw Q40 and trace every distance and predecessor update.
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.
Keep learning
UP LT Grade CS PYQs: A Topic-Wise Practice System
Stop solving previous papers once and forgetting the mistakes. This system indexes every question by concept, schedules three attempts and turns each error into a measurable repair task.
IBPS PO Previous Year Paper Analysis: Build Your Own Topic-wise Weightage Tally
IBPS does not publish a topic-wise weightage table, so build one you can defend: one column per shift, one label per question, and every column totalling its section's question count.
SSC CGL Previous Year Paper Analysis: Topic-wise Question Distribution in Tier 1
We counted topic recurrence across our question bank built from SSC CGL previous year papers. Section by section, here is which Tier 1 topics repeat the most in quant, reasoning, English and General Awareness, and the study order that follows from the data.
UPPSC Teaching PYQ Analysis: Build an Error-Led Revision Plan
Learn a repeatable way to verify teaching PYQs, separate topic from reasoning demand, diagnose errors and convert the evidence into next week's study calendar.





