###### GATE 2017 [Set-1]

October 12, 2023###### UGC NET CS 2014 Dec-Paper-2

October 12, 2023# GATE 2017 [Set-1]

Question 5 |

Consider the following table

Match the algorithm to design paradigms they are based on:

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

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

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

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

Question 5 Explanation:

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

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.

(Q) QuickSort is a Divide and Conquer algorithm.

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

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.

Correct Answer: C

Question 5 Explanation:

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

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.

(Q) QuickSort is a Divide and Conquer algorithm.

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

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.

Subscribe

Login

0 Comments