Given below are some algorithms, and some algorithm design paradigms. 1.…
2015
Given below are some algorithms, and some algorithm design paradigms.
1. Dijkstra’s Shortest Path | i. Divide and Conquer |
2. Floyd-Warshall algorithm to compute all pairs shortest path | ii. Dynamic Programming |
3. Binary search on a sorted array | iii. Greedy design |
4. Backtracking search on a graph | iv. Depth-first search |
v. Breadth-first search |
Match the above algorithms on the left to the corresponding design paradigm they follow.
- A.
1-i, 2-iii, 3-i, 4-v.
- B.
1-iii, 2-iii, 3-i, 4-v.
- C.
1-iii, 2-ii, 3-i, 4-iv.
- D.
1-iii, 2-ii, 3-i, 4-v.
Attempted by 155 students.
Show answer & explanation
Correct answer: C
Correct matching and why:
Dijkstra’s Shortest Path — Greedy design: it repeatedly picks the closest unvisited vertex and makes locally optimal choices to fix shortest distances.
Floyd–Warshall (all‑pairs shortest path) — Dynamic Programming: it builds solutions for longer paths using solutions for shorter subpaths (overlapping subproblems).
Binary search on a sorted array — Divide and Conquer: it halves the search interval each step and recurses/iterates on one half.
Backtracking search on a graph — Depth‑first search: backtracking explores a branch deeply, using recursion or a stack, and backtracks when a path fails.