GATE Algorithms and Data Structures 2

Question 1

What is the time complexity of the Floyd-Warshall algorithm for computing all-pairs shortest paths in a graph with V vertices?

Accepted Answer

O(V³)

Answer

O(V²)

Answer

O(V² log V)

Answer

O(V² + E)

Question 2

The 0/1 Knapsack problem with n items and capacity W, solved using dynamic programming, has time complexity:

Accepted Answer

O(n × W)

Answer

O(n + W)

Answer

O(n log W)

Answer

O(2ⁿ)

Question 3

Dijkstra's single-source shortest path algorithm produces incorrect results when the graph contains:

Accepted Answer

Negative weight edges

Answer

Directed edges

Answer

Dense connectivity

Answer

Disconnected components

Question 4

What is the time complexity of Prim's Minimum Spanning Tree algorithm when implemented with a binary min-heap?

Accepted Answer

O(E log V)

Answer

O(V²)

Answer

O(V log V)

Answer

O(E + V)

Question 5

Which of the following is a capability of the Bellman-Ford shortest path algorithm that Dijkstra's algorithm lacks?

Accepted Answer

Detects negative weight cycles

Answer

Handles only positive weights

Answer

Runs faster than Dijkstra's algorithm

Answer

Works only on undirected graphs

Question 6

What is the recurrence relation that correctly describes the number of comparisons C(n) in Merge Sort?

Accepted Answer

C(n) = 2C(n/2) + n

Answer

C(n) = C(n−1) + n

Answer

C(n) = C(n/2) + 1

Answer

C(n) = C(n−1) + C(n−2)

Question 7

Which algorithmic paradigm is used to efficiently solve the Longest Common Subsequence (LCS) problem?

Accepted Answer

Dynamic Programming

Answer

Greedy

Answer

Backtracking

Answer

Divide and Conquer