Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
126. Given below are some algorithms, and some algorithm design paradigms.
| List-I | List-II | ||
| A. | Dijkstra's Shortest PathDijkstra's Shortest Path | 1. | Divide and Conquer |
| B. | Floyd-Warshall algorithm to compute all pairs shortest path | 2. | Dynamic Programming |
| C. | Binary search on a sorted array | 3. | Greedy design |
| D. | Backtracking search on a graph | 4. | Depth-first search |
| 5. | Breadth-first search | ||
Match the above algorithms (List-I) to the
corresponding design paradigm (List-II) they
follow.
Codes:
| A | B | C | D | |
| (a) | 1 | 3 | 1 | 5 |
| (b) | 3 | 3 | 1 | 5 |
| (c) | 3 | 2 | 1 | 4 |
| (d) | 3 | 2 | 1 | 5 |
- Option : C
- Explanation : Dijkstr a use greedy approach, warshals use dynamic programming approach, Binary search is based on divide and conquer and Backtracking is depth first search.
- Option : D
- Explanation : Suppose we want to search y.
No of comparision
= 1× Probability of 1st element being x
+ 2 * Probability of 2nd element being x.
+ 3* Probability of 3rd element being x.
+ n* Probability of nth element being x.
