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

Consider the following table Match the algorithm to 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)
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.
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.