Skip to content
GATETECH
Official PYQ · 2015Set 2 · Q36Algorithm Design: Greedy TechniquesMCQ1 mark

GATE CS 2015 Set 2 Q36 — Algorithm Design: Greedy Techniques

Explain with AI

Given below are some algorithms, and some algorithm design paradigms. 1.Dijkstra’s Shortest Pathi.Divide and Conquer2.Floyd-Warshall algorithm to computeall pair shortest pathii.Dynamic Programming3.Binary search on a sorted arrayiii.Greedy design4.Backtracking search on a graphiv.Depth-first searchv.Breadth-first search\begin{array}{|ll|ll|}\hline \text{1.} & \text{Dijkstra's Shortest Path} & \text{i.} & \text{Divide and Conquer} \\ \hline \text{2.} & \text{Floyd-Warshall algorithm to compute} \\& \text{all pair shortest path} & \text{ii.}& \text{Dynamic Programming} \\ \hline \text{3.}& \text{Binary search on a sorted array} & \text{iii.} & \text{Greedy design} \\ \hline \text{4.} & \text{Backtracking search on a graph} &\text{iv.} & \text{Depth-first search} \\ \hline & &\text{v.} & \text{Breadth-first search} \\ \hline \end{array}
Match the above algorithms on the left to the corresponding design paradigm they follow.

Choose one option
View worked solution

Answer: C

We can determine the correct matching by analyzing the design paradigm of each algorithm:

  • 1. Dijkstra's Shortest Path: This algorithm finds the single-source shortest path by greedily selecting the vertex with the minimum tentative distance at each step. Thus, it follows the Greedy design (iii).
  • 2. Floyd-Warshall Algorithm: This algorithm computes all-pairs shortest paths by solving overlapping subproblems (considering paths through a subset of intermediate vertices 1,2,…,k1, 2, \dots, k). Thus, it uses Dynamic Programming (ii).
  • 3. Binary Search: It divides the sorted array into two halves, compares the target with the middle element, and recursively searches in one of the halves. Thus, it follows the Divide and Conquer (i) paradigm.
  • 4. Backtracking Search: Backtracking explores a graph or state-space tree by going as deep as possible along each branch before backtracking. This traversal strategy is fundamentally a Depth-first search (iv).

Combining these matches:

  • 1→iii1 \rightarrow \text{iii}
  • 2→ii2 \rightarrow \text{ii}
  • 3→i3 \rightarrow \text{i}
  • 4→iv4 \rightarrow \text{iv}

This corresponds to the match: 1-iii, 2-ii, 3-i, 4-iv, which is Option C.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Greedy Techniques questions