retagged by
6,943 views
25 votes
25 votes

Consider the following table:

$$\begin{array}{|l|}\hline \textbf {Algorithms} & \textbf{Design Paradigms } & \\\hline  \text{P. Kruskal} & \text{i. Divide and Conquer}   \\\hline  \text{Q. Quicksort} & \text{ii. Greedy}  \\\hline  \text{R. Floyd-Warshall} & \text{iii. Dynamic Programming}\\\hline  \end{array}$$

Match the algorithms to the design paradigms they are based on.

  1. $(P) \leftrightarrow (ii), (Q) \leftrightarrow (iii), (R) \leftrightarrow (i)$
  2. $(P) \leftrightarrow (iii), (Q) \leftrightarrow (i), (R) \leftrightarrow (ii)$
  3. $(P) \leftrightarrow (ii), (Q) \leftrightarrow (i), (R) \leftrightarrow (iii)$
  4. $(P) \leftrightarrow (i), (Q) \leftrightarrow (ii), (R) \leftrightarrow (iii)$
retagged by

7 Answers

Best answer
28 votes
28 votes

In Kruskal, in every iteration, an edge of the most minimum weight (greediest) possible is selected and added to MST construction. Hence, greedy.

In Quick Sort, we partition the problem into subproblems, solve them and then combine. Hence, it is Divide & Conquer.

Floyd-Warshall uses Dynamic programming.

Hence, correct answer is : OPTION (C).

edited by
7 votes
7 votes

quicksort --->divide and conquer

Kruskal --->greedy ( Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step).

Floyd warshall--->dynamic   (Dynamic Programming. Set 16 (Floyd Warshall Algorithm) The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph).

hence ans is C.

edited by
5 votes
5 votes
kruskals algorithm: It is used to find the minimum spanning tree of a given Graph, this algorithm follows "greedy approach" because the basic idea is find out the minimum weight of edges in MST.

Quick sort: It follows divide and conquer approach.

Floyd-Warshall : It is used to find all pair shortest path in Graph. It works on dynamic programming paradigm..

Hence C will be its answer....
4 votes
4 votes
option (C)

KRUSKAL -->  greedy approach

QUICKSORT --> DIVIDE and CONQUER

Floyd-warshal --> Dynamic programming
Answer:

Related questions

25 votes
25 votes
3 answers
1
go_editor asked Feb 12, 2015
6,931 views
Given below are some algorithms, and some algorithm design paradigms.$$\begin{array}{ll|ll}\hline \text{1.} & \text{Dijkstra's Shortest Path} & \text{i.} & \text{Divide a...
21 votes
21 votes
3 answers
2
Kathleen asked Sep 29, 2014
4,978 views
The correct matching for the following pairs is$$\begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \...
11 votes
11 votes
1 answer
3
makhdoom ghaya asked Nov 19, 2016
5,833 views
Match the pairs in the following questions:$$\begin{array}{|ll|ll|}\hline (a) & \text{Strassen's matrix multiplication algorithm} & (p) & \text{Greedy method} \\\hline (...
26 votes
26 votes
4 answers
4
makhdoom ghaya asked Feb 12, 2015
5,514 views
Match the following:$$\begin{array}{|ll|ll|}\hline \text{P.} & \text{Prim's algorithm for minimum spanning tree} & \text{i.} & \text{Backtracking} \\\hline \text{Q.}...