search
Log In
3 votes
801 views

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$
in Algorithms
edited by
801 views

3 Answers

1 vote
Ans. A

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

Related questions

0 votes
2 answers
1
363 views
Consider the following code segment to find the $n^{th}$ Fibonacci number: Fib(n) { if(n==0) {return 0;} if(n==1) {return 1;} else { return(Fib(n-1) + Fib(n-2)); } } The time complexity of the above code and time complexity of the same problem solved using dynamic programming is______ $A)O(n^{2}),O(n)$ $B)O(2^{n}),O(n)$ $C)O(2^{n}),O(n^{2})$ $D)$None of the above
asked Nov 13, 2018 in Algorithms Lakshman Patel RJIT 363 views
1 vote
1 answer
2
888 views
Unlike greedy algorithms, dynamic programming method always provide correct/optimal solution. Is the above statement correct?
asked Dec 13, 2017 in Algorithms Tuhin Dutta 888 views
2 votes
3 answers
3
482 views
Match List-I with List-II: ... (c)-(i); (d)-(ii) (a) - (ii); (b)-(i); (c)-(iv); (d)-(iii) (a) - (iii); (b)-(i); (c)-(iv); (d)-(ii)
asked Jul 2, 2019 in Algorithms Arjun 482 views
3 votes
2 answers
4
813 views
There are many sorting algorithms based on comparison. The running time of heapsort algorithm is $O(n \text{lg}n)$. Like $P$, but unlike $Q$, heapsort sorts in place where $(P,Q)$ is equal to Merge sort, Quick sort Quick sort, insertion sort Insertion sort, Quick sort Insertion sort, Merge sort
asked Jul 2, 2019 in Algorithms Arjun 813 views
...