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

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:

Accepted Answer

O(n × W)

Answer

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:

Accepted Answer

Negative weight edges

Answer

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?

Accepted Answer

O(E log V)

Answer

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?

Accepted Answer

Detects negative weight cycles

Answer

Bellman-Ford performs V−1 relaxation passes; if a V-th pass still reduces some distance, a negative weight cycle is detected.

(GATE) Graduate Aptitude Test in Engineering Practice Test

(GATE) Graduate Aptitude Test in Engineering Practice Test

GATE Algorithms and Data Structures 2