UGC NET CSE | January 2017 | Part 3 | Question: 36

Question

Match the following with respect to algorithm paradigms :

$\begin{array}{clcl} & \textbf{List-I} & {} & \textbf{List-II} \\ \text{a.} & \text{Merge sort} & \text{i.} & \text{Dynamic programming}  \\  \text{b.} & \text{Huffman coding} & \text{ii.} & \text{Greedy approach} \\ \text{c.} & \text{Optimal polygon triangulation} & \text{iii.} & \text{Divide and conquer} \\ \text{d.} & \text{Subset sum problem} & \text{iv.} & \text{Back tracking} \\  \end{array}$

$\textbf{Codes :}$

• A. $\text{a-iii, b-i, c-ii, d-iv}$
• B. $\text{a-ii, b-i, c-iv, d-iii}$
• C. $\text{a-ii, b-i, c-iii, d-iv}$
• D. $\text{a-iii, b-ii, c-i, d-iv}$

Comments

Merge sort    - Divide and conquer  

Huffman coding  -Greedy approach

Optimal polygon triangulation    -Back tracking                

  Subset sum problem   - Dynamic programming

Answer 1

it is straight from book and no explanation required i think

Mere sort-> D &Q

Huffman ->Greedy

Subset Sum->

already we got the answer..only D matches this two options

so D is correct answer

Answer 2

Ans will be  4 

Merge sort                              ----->   iii Divide and conquer

Huffman coding                       ----->   ii Greedy approach

Optimal polygon triangulation    -------> i. Dynamic Programming

Subset sum problem                -------> iv. Back tracking 

Greedy algorithm is an algorithm that follows the problem solving mechanism  of making the locally optimal solution at each stage with thinking  of finding a global optimum solution for the problem and In Huffman coding in every stage we try to find the the prefix free binary code and try to minimize expected code word for optimum solution for compress the data.

Answer 3

Merge sort                              ----->   iii Divide and conquer

Huffman coding                       ----->   ii Greedy approach

Optimal polygon triangulation    -------> i. Dynamic Programming

Subset sum problem                -------> iv. Back tracking 

just match first 2..

Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most respectedalgorithms. Merge sort first divides the array into equal halves and then combines them in a sorted manner.

Greedy algorithm is an algorithm that follows the problem solving mechanism  of making the locally optimal solution at each stage with thinking  of finding a global optimum solution for the problem and In Huffman coding in every stage we try to find the the prefix free binary code and try to minimize expected code word for optimum solution for compress the data.

Answer 4

We can do this question simply Elimination

Merge sort is based on Divide and Conquer because it Firstly divide then merge

So ii and iii eliminated

Huffman coding is a greeady approach

So option i is eliminated

Answer is option D