The correct matching for the following pairs is (A) All pairs shortest path…
1997
The correct matching for the following pairs is
(A) All pairs shortest path (1) Greedy
(B) Quick Sort (2) Depth-First search
(C) Minimum weight spanning tree (3) Dynamic Programming
(D) Connected Components (4) Divide and and Conquer- A.
(A-2, B-4, C-1, D-3 )
- B.
(A-3,B-4,C-1, D-2 )
- C.
(A-3 ,B-4 ,C-2 ,D-1 )
- D.
(A-4 ,B-1 ,C-2 ,D-3 )
Attempted by 8 students.
Show answer & explanation
Correct answer: B
Let's look at the core design strategy behind each algorithm:
(A) All pairs shortest path ⟶ (3) Dynamic Programming
The standard algorithm for finding the shortest paths between all pairs of vertices is the Floyd-Warshall algorithm. It breaks the problem down into overlapping subproblems (finding paths using intermediate vertices 1, 2, ......, k) and stores the results in a table, which is a textbook definition of Dynamic Programming.
(B) Quick Sort ⟶ (4) Divide and Conquer
Quick Sort works by picking an element as a pivot, partitioning the array around that pivot (Dividing), and then recursively sorting the left and right sub-arrays (Conquering).
(C) Minimum weight spanning tree ⟶ (1) Greedy
Algorithms like Kruskal's and Prim's are used to find a Minimum Spanning Tree (MST). Both make locally optimal choices at each step (always picking the cheapest available valid edge) with the goal of finding a globally optimal minimum weight, which is the definition of a Greedy approach.
(D) Connected Components ⟶ (2) Depth-First search
To find all connected components in an undirected graph, you start at an unvisited node and use a graph traversal technique like Depth-First Search (DFS) or Breadth-First Search (BFS) to visit all reachable nodes, marking them as part of the same component before moving to the next unvisited node.