22 votes

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.

- $(P) \leftrightarrow (ii), (Q) \leftrightarrow (iii), (R) \leftrightarrow (i)$
- $(P) \leftrightarrow (iii), (Q) \leftrightarrow (i), (R) \leftrightarrow (ii)$
- $(P) \leftrightarrow (ii), (Q) \leftrightarrow (i), (R) \leftrightarrow (iii)$
- $(P) \leftrightarrow (i), (Q) \leftrightarrow (ii), (R) \leftrightarrow (iii)$

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

7 votes

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

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

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

option (C)

KRUSKAL --> greedy approach

QUICKSORT --> DIVIDE and CONQUER

Floyd-warshal --> Dynamic programming

KRUSKAL --> greedy approach

QUICKSORT --> DIVIDE and CONQUER

Floyd-warshal --> Dynamic programming

1 vote

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

1 vote

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

(Q) QuickSort is a Divide and Conquer algorithm.

(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.

1 vote

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

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