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

option d

a) merge ------------------------------------.> iii) Divide and conquer 

b) Huffman coding -------------------------> ii)Greedy approach 

c)Optimal polygon triangulation -------->i) Dynamic programming 

d)Subset sum problem------------------->iv)Backtracking

• optimal polygon triangulation is similar to matrix chain multiplication.
• we will solve the Subset Sum problem using a backtracking as well as dynamic prog.

so the best matching is option d

Answer 2

 

Merge sort--Divide and conquer

Huffman coding--Greedy approach

Optimal polygon triangulation--Back tracking

Subset sum problem--Dynamic programming