edited by
5,537 views
3 votes
3 votes

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?

  1. Only $S_1$
  2. Only $S_2$
  3. Both $S_1$ and $S_2$
  4. Neither $S_1$ nor $S_2$
edited by

3 Answers

2 votes
2 votes
Ans. A

Both Dp and greedy algorithms find optimal substructure in the problem but only DP uses the bottom up approach.
0 votes
0 votes
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
0 votes
0 votes
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.
Answer:

Related questions

1 votes
1 votes
1 answer
2
Tuhin Dutta asked Dec 13, 2017
6,300 views
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution.Is the above statement correct?
2 votes
2 votes
2 answers
3
Arjun asked Jul 2, 2019
1,633 views
Match List-I with List-II:$$\begin{array}{|c|c|c|c|} \hline {} & \text{List-I} & {} & \text{List-II} \\ \hline (a) & \text{Prim’s algorithm} & (i) & O(V^3 \log V) \\ \h...