Algorithms for the GATE Exam — Indian candidates

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.
• 6For candidates in India, GATE test windows are typically denser in the spring; book test centres in metro cities (Delhi, Mumbai, Bengaluru, Chennai, Kolkata) early to secure preferred dates.

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²).

Frequently asked questions

Related study guides

• Data Structures for GATE (India)Another GATE topic for Indian candidates
• Theory of Computation for GATE (India)Another GATE topic for Indian candidates
• Computer Organization & Architecture for GATE (India)Another GATE topic for Indian candidates
• Operating Systems for GATE (India)Another GATE topic for Indian candidates
• Computer Networks for GATE (India)Another GATE topic for Indian candidates
• Algorithms for GATE — U.S. candidatesSame Algorithms topic, different locale framing
• Algorithms for GATE — U.K. candidatesSame Algorithms topic, different locale framing
• Algorithms for GATE — Filipino candidatesSame Algorithms topic, different locale framing