GATE Algorithms and Data Structures 2 â Questions and Answers
Question 1: What is the time complexity of the Floyd-Warshall algorithm for computing all-pairs shortest paths in a graph with V vertices?
- O(V²)
- O(V² log V)
- O(VÂł) (Correct answer)
- O(V² + E)
Correct answer: O(VÂł)
Floyd-Warshall uses three nested loopsâone for each possible intermediate vertex and one for each pair of source/destination verticesâresulting in O(VÂł) time.
Question 2: The 0/1 Knapsack problem with n items and capacity W, solved using dynamic programming, has time complexity:
- O(n + W)
- O(n Ă W) (Correct answer)
- O(n log W)
- O(2âż)
Correct answer: O(n Ă W)
The DP table has n rows and W+1 columns, and each of the nĂW cells is filled in O(1) time, giving O(n Ă W) total.
Question 3: Dijkstra's single-source shortest path algorithm produces incorrect results when the graph contains:
- Directed edges
- Negative weight edges (Correct answer)
- Dense connectivity
- Disconnected components
Correct answer: Negative weight edges
Dijkstra's greedy strategy assumes that once a node's distance is finalized it cannot improve, which breaks when negative edges allow a longer path to have a shorter total weight.
Question 4: What is the time complexity of Prim's Minimum Spanning Tree algorithm when implemented with a binary min-heap?
- O(V²)
- O(E log V) (Correct answer)
- O(V log V)
- O(E + V)
Correct answer: O(E log V)
Each of the E edges triggers at most one decrease-key operation costing O(log V), and extracting V vertices costs O(V log V), giving O(E log V) overall.
Question 5: Which of the following is a capability of the Bellman-Ford shortest path algorithm that Dijkstra's algorithm lacks?
- Handles only positive weights
- Detects negative weight cycles (Correct answer)
- Runs faster than Dijkstra's algorithm
- Works only on undirected graphs
Correct answer: Detects negative weight cycles
Bellman-Ford performs Vâ1 relaxation passes; if a V-th pass still reduces some distance, a negative weight cycle is detected.
Question 6: What is the recurrence relation that correctly describes the number of comparisons C(n) in Merge Sort?
- C(n) = C(nâ1) + n
- C(n) = 2C(n/2) + n (Correct answer)
- C(n) = C(n/2) + 1
- C(n) = C(nâ1) + C(nâ2)
Correct answer: C(n) = 2C(n/2) + n
Merge Sort splits into two subproblems of size n/2 (cost 2C(n/2)) and then merges the two halves in O(n) comparisons, giving C(n) = 2C(n/2) + n.
Question 7: Which algorithmic paradigm is used to efficiently solve the Longest Common Subsequence (LCS) problem?
- Greedy
- Backtracking
- Dynamic Programming (Correct answer)
- Divide and Conquer
Correct answer: Dynamic Programming
LCS exhibits optimal substructure and overlapping subproblems, so dynamic programming fills a 2D table in O(mĂn) time rather than recomputing subproblems recursively.
GATE Algorithms and Data Structures 2
What is the time complexity of the Floyd-Warshall algorithm for computing all-pairs shortest paths in a graph with V vertices?