Algorithms for the GATE Exam

Common failure modes

These are the patterns that cause most candidates to lose marks on this topic. Recognising them in advance is half the work.

• !Solving recurrences incorrectly using the Master Theorem — misidentifying which case applies
• !Confusing time complexity of graph algorithms (Dijkstra with a binary heap is O((V+E) log V), not O(V²))
• !Proposing greedy solutions without proving the greedy-choice and optimal-substructure properties
• !Using overlapping-subproblem intuition but defining the wrong DP state (leading to exponential states)
• !Forgetting that Bellman-Ford handles negative edges but not negative cycles; Dijkstra fails on negative edges

Study tips

• 1Memorise the Master Theorem: T(n) = aT(n/b) + f(n). Know all three cases and their conditions, including the 'regularity condition' for Case 3.
• 2Drill classic DP problems: 0/1 knapsack, longest common subsequence, matrix chain multiplication, and coin change. GATE recycles these patterns in new settings.
• 3For sorting, know the lower bound Ω(n log n) for comparison-based sorting, and the O(n) cases: counting sort, radix sort, bucket sort.
• 4Trace Dijkstra and Bellman-Ford step-by-step on a small graph (5 nodes) until you can do it without notes.
• 5Practice asymptotic notation questions: ranking functions by growth rate is a reliable 1-mark source.

Sample GATE Algorithms questions

These sample items mirror the format and difficulty of real GATE questions. Practice with thousands more on the free Koydo question bank.

1. 1

   Which of the following algorithms does NOT work correctly on graphs with negative-weight edges?

   • ABellman-Ford
   • BFloyd-Warshall
   • CDijkstra's algorithmCorrect
   • DDFS-based topological sort with relaxation
   Why this answer?

   (GATE CS style) Dijkstra's algorithm uses a greedy approach that assumes once a vertex is settled its distance is final. A negative-weight edge can later provide a shorter path, violating this assumption. Bellman-Ford and Floyd-Warshall handle negative edges (but not negative cycles).

2. 2

   The recurrence T(n) = 2T(n/2) + n has solution:

   • AO(n)
   • BO(n log n)Correct
   • CO(n²)
   • DO(log n)
   Why this answer?

   (GATE CS style) By the Master Theorem: a = 2, b = 2, f(n) = n. n^(log_b a) = n^1 = n. Since f(n) = Θ(n^(log_b a)), this is Case 2, giving T(n) = Θ(n log n).

3. 3

   The best-case time complexity of QuickSort is:

   • AO(n²)
   • BO(n log n)Correct
   • CO(n)
   • DO(log n)
   Why this answer?

   (GATE CS style) In the best case, each partition splits the array into two equal halves, giving the recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n). Worst-case (always picking min/max as pivot) is O(n²).