60 solved GATE CS questions on Algorithms, drawn from 10 exam years and grouped by year. Every question shows the official answer and a step-by-step solution.
Want to practise this topic and ask follow-up questions? Explore Success Tracker.
Revision companion
Identify the input model, required output, and property that makes an algorithm correct before calculating time or space. These selected revision notes connect asymptotic analysis, graph traversal, and design techniques. Reproduce the small examples by hand, explaining each decision before moving to larger practice problems.
Our study notes and original examples support the PYQs below; they are not official exam questions or a replacement for the current syllabus.
O denotes an asymptotic upper bound, Ω a lower bound, and Θ a tight bound. These do not inherently mean worst, best, or average case. Define the cost function and input size; graphs often require both vertex count V and edge count E.
Check yourself: Are you bounding worst-case cost or an expectation?
Separate recursive work from work outside recursive calls. In T(n) = 2T(n/2) + n for powers of two, each internal level contributes n, across log₂ n levels. Include leaf costs for an exact expression, not just a growth rate.
Check yourself: Does the expression satisfy the recurrence and base case?
BFS uses a FIFO queue to discover vertices by edge-count distance. Dijkstra selects the smallest tentative weighted distance; its standard correctness argument requires nonnegative weights. With adjacency lists, BFS takes O(V + E), while binary-heap Dijkstra takes O((V + E) log V).
Check yourself: Are you minimizing hops or weight, and are negative weights possible?
Justify greedy choices through an exchange argument, cut property, or invariant showing an optimal solution can include them. For maximizing the number of nonoverlapping intervals, earliest finish time leaves room for later intervals; earliest start time need not maximize the count.
Check yourself: Can your choice replace one in an optimal solution without worsening it?
Define each state's meaning, base cases, and dependency order before writing transitions. For 0/1 knapsack with a one-dimensional capacity array, descending capacity prevents reuse of the current item. Ascending capacity would permit repeated use within the same item pass.
Check yourself: Could the state you read already include the current item?
Original teaching example · not a PYQ
Original mini-example: a directed graph has vertices S, A, T and exactly these edges: S → T (weight 7), S → A (weight 2), A → T (weight 3). Compare BFS's hop-count path from S to T with Dijkstra's weighted shortest path.
BFS: one hop, weight 7. Dijkstra: weight 5 via A.
For n a positive power of two (including 1), solve T(1) = 1 and T(n) = 2T(n/2) + n for n > 1 exactly. Find T(8).
T(n) = n log₂ n + n; T(8) = 32.
There are log₂ n internal levels contributing n each, plus n unit-cost leaves. For n = 8, this totals 24 + 8 = 32. The expression also returns 1 at the base case.
Supplemental reading, not an official GATE reading list or an endorsement of these notes.
Free supplemental MIT lectures, notes, and assignments. Explore graph search, shortest paths, and dynamic programming to practice both reasoning and implementation.
This page shows 60 recent questions from the released archive, newest first. For older questions and complete papers, browse all GATE CS papers. Questions can carry more than one subject tag; counts are not marks weightage.
G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length…MCQ · +2 marks · HardG(V, E) be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST)…MSQ · +2 marks · MediumG(V, E) as input, where and are the…MSQ · +2 marks · HardG(V, E) be an undirected and unweighted graph with 100 vertices. Let denote the number of edges in a shortest path between vertices and …MCQ · +2 marks · Mediumswap(&x, &y) exchanges the contents of x and y. [code] The output of the program is ________.NAT · +2 marks · MediumContinue learning with Success Tracker
Reading a solution is a useful start. In Success Tracker, you can attempt questions yourself, review mistakes and return to the topics that need another pass.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.