The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 votes

Consider the following table:

$$\begin{array}{|l||l|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)$
asked in Algorithms by Loyal (6.8k points)
edited by | 2.7k views

4 Answers

+19 votes
Best answer

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)$.

answered by Active (3.4k points)
edited by
+6 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.

answered by Boss (47.1k points)
edited by
+4 votes
option (C)

KRUSKAL -->  greedy approach


Floyd-warshal --> Dynamic programming
answered by Junior (555 points)
+4 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....
answered by Boss (40.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,532 questions
54,123 answers
71,044 users