Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
121. Match the pairs in the following:
| List-I | List-II | ||
| A. | All pairs shortest paths | P. | Greedy |
| B. | Quick Sort | Q. | Depth-First search |
| C. | Minimum weight spanning tree | R. | Dynamic Programming |
| D. | Connected Components | S. | Divide and Conquer |
- Option : D
- Explanation : The statement inside the for loop is similar to X– OR operation such that the set obtained is (X ∩ Y') ∪ (X' ∩ Y). It is equivalent to (X – Y) ∪ (Y – X)
- Option : A
- Explanation : By definition, T(9) = Dist. From 9 to 100 As given, T(9) = 1+min (T(y), T()(z) = 1 + min (Dist. from y to 100, Dist. From z to 100) ⇒ 1 = Dist. from 9 to y/Dist. From 9 to z ⇒ There are only two such values-one is the simple one step on number line i.e. 10, and the other is the shortcut associated with 9 i.e. 15. ⇒ Therefore, y and z are 10 and 15 (in any order) ⇒ Product yz = 150.
| List-I | List-II | ||
| A. | Prim's algorithm for minimum spanning tree | 1. | Backtracking |
| B. | Floyd-Warshall algorithm for all pairs shortest paths | 2. | Greedy method |
| C. | Mergesort | 3. | Dynamic programming |
| D. | Hamiltonian circuit | 4. | Divide and Conquer |
Codes:
| A | B | C | D | |
| (a) | 3 | 2 | 4 | 1 |
| (b) | 1 | 2 | 4 | 3 |
| (c) | 2 | 3 | 4 | 1 |
| (d) | 2 | 1 | 3 | 4 |
- Option : C
- Explanation : Prims algorithm is greedy method because it choose minimum distance node. Floyd warshal’s is dynamic because it changes the distance on each iteration. Merge sort is divide and conquer because it divide the whole list is sublist and combine after sorting each sublist Hamiltonian cycle is based on backtracking.
