UGC NET CSE | June 2019 | Part 2 | Question: 68

Question

Consider the following steps:

$S_1$: Characterize the structure of an optimal solution

$S_2$: Compute the value of an optimal solution in bottom-up fashion

Which of the following step(s) is/are common to both dynamic programming and greedy algorithms?

• A. Only $S_1$
• B. Only $S_2$
• C. Both $S_1$ and $S_2$
• D. Neither $S_1$ nor $S_2$

Answer 1

Ans. A

Both Dp and greedy algorithms find optimal substructure in the problem but only DP uses the bottom up approach.

Answer 2

Opton (A): only S1

Because both greedy algo and dynamic programming finds the optimal solution for their problems but ,

only dynamic programming uses bottom-up approach

whereas,greedy algo uses top-bottom approach

Answer 3

option A) Only S1 , because both dynamic and greedy finds optimal solution but only dynamic programming computes the value by following a Bottom up approach.