3.1k views

Consider the following table:$$\begin{array}{|ll|ll|}\hline \rlap{\textbf {Algorithms}} & & \rlap{\textbf{Design Paradigms }} & \\\hline \text{P.} & \text{Kruskal} & \text{i.}& \text{Divide and Conquer} \\\hline \text{Q.} & \text{Quicksort} & \text{ii.}& \text{Greedy} \\\hline \text{R.} & \text{Floyd-Warshall} & \text{iii.}& \text{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)$

edited | 3.1k views

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

by Active
edited

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.

by Boss
edited by
option (C)

KRUSKAL -->  greedy approach

QUICKSORT --> DIVIDE and CONQUER

Floyd-warshal --> Dynamic programming
by Junior
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....
by Boss

Answer will be Option C .

Quicksort is a divide and conquer technique.
while Kruskal algorithms work to find the minimum weight so it takes a greedy approach .
Floyd Warshell for all-pair shortest path uses Dynamic programming with a time complexity o(n3).

by
(P) Kruskal’s and Prim’s algorithms for finding Minimum Spanning Tree(MST). To find MST we are using greedy technique.
(Q) QuickSort is a Divide and Conquer algorithm.
(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.
by Junior
Some important points regarding Greedy Vs Dynamic Programming
Greedy: →
It always gives polynomial time complexity
→ It is not an optimal
→ It always selects only either minimum or maximum among all possibilities
→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,
Dynamic Programming:
→ It gives either polynomial or exponential time complexity.
→ It gives always an optimal result.
→ It checks all possibilities of a problem.
→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc..,
by Junior