Huffman coding -Greedy approach

Optimal polygon triangulation -Back tracking

Subset sum problem - Dynamic programming

Dark Mode

980 views

0 votes

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

- $\text{a-iii, b-i, c-ii, d-iv}$
- $\text{a-ii, b-i, c-iv, d-iii}$
- $\text{a-ii, b-i, c-iii, d-iv}$
- $\text{a-iii, b-ii, c-i, d-iv}$

0 votes

*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