984 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

it is straight from book and no explanation required i think

Mere sort-> D &Q

Huffman ->Greedy

Subset Sum->

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.

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 respectedalgorithmsMerge 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.

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

1
2,084 views