980 views

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 :}$

1. $\text{a-iii, b-i, c-ii, d-iv}$
2. $\text{a-ii, b-i, c-iv, d-iii}$
3. $\text{a-ii, b-i, c-iii, d-iv}$
4. $\text{a-iii, b-ii, c-i, d-iv}$

### 1 comment

Merge sort    - Divide and conquer

Huffman coding  -Greedy approach

Optimal polygon triangulation    -Back tracking

Subset sum problem   - Dynamic programming

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

Merge sort--Divide and conquer

Huffman coding--Greedy approach

Optimal polygon triangulation--Back tracking

Subset sum problem--Dynamic programming

5
2,070 views