Consider the following table: Match the algorithms to the design paradigms they are based on. A) (P) ↔ (ii), (Q) ↔ (iii), (R) ↔ (i) B) (P) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii) C) (P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii) D) (P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii)

Official answer: C) (P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii). Explanation: Let us analyze the design paradigm for each algorithm: 1. Kruskal's algorithm (P): It finds a Minimum Spanning Tree (MST) by sorting edges and greedily adding the minimum weight edge that does not form a cycle. Hence, (P) ↔ (ii) (Greedy). 2. Quicksort (Q): It partitions an array into two sub-arrays around a pivot and recursively sorts the sub-arrays. Hence, (Q) ↔ (i) (Divide and Conquer). 3. Floyd-Warshall (R): It solves the all-pairs shortest paths problem by breaking it down into subproblems using dynamic programming. Hence, (R) ↔ (iii) (Dynamic Programming). Thus, the correct matching is (P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii), which corresponds to option (C).

A) (P) ↔ (ii), (Q) ↔ (iii), (R) ↔ (i)

B) (P) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii)

D) (P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii)

Algorithm Design Techniques

GATE CSE 2017 Set 1 · Q5

MCQ1 markEasy

Time00:00

Consider the following table: Match the algorithms to the design paradigms they are based on.

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: C) (P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii)

Algorithm Design Techniques

Let us analyze the design paradigm for each algorithm:

Kruskal's algorithm (P): It finds a Minimum Spanning Tree (MST) by sorting edges and greedily adding the minimum weight edge that does not form a cycle. Hence, $(\text{P}) \leftrightarrow (\text{ii})$ (Greedy).
Quicksort (Q): It partitions an array into two sub-arrays around a pivot and recursively sorts the sub-arrays. Hence, $(\text{Q}) \leftrightarrow (\text{i})$ (Divide and Conquer).
Floyd-Warshall (R): It solves the all-pairs shortest paths problem by breaking it down into subproblems using dynamic programming. Hence, $(\text{R}) \leftrightarrow (\text{iii})$ (Dynamic Programming).

Thus, the correct matching is $(\text{P}) \leftrightarrow (\text{ii}),\ (\text{Q}) \leftrightarrow (\text{i}),\ (\text{R}) \leftrightarrow (\text{iii})$ , which corresponds to option (C).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Algorithm Design Techniques previous year question is Q5 of the GATE CSE 2017 Set 1 paper. Find more GATE CSE PYQs on Algorithm Design Techniques in Algorithms, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Algorithm Design Techniques PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Algorithm Design Techniques in GATE CSE

Algorithm Design Techniques has 6 GATE CSE PYQs across 6 papers from 2011 to 2017. 2 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2017 Set 1.

How GATE tests Algorithm Design Techniques

More from GATE CSE 2017 Set 1

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.