The Gateway to Computer Science Excellence

+20 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)$

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

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

+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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,651 questions

56,214 answers

194,173 comments

95,427 users