The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

+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.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,123 answers

187,319 comments

71,044 users