1
$\begingroup$

I have two True or False questions in my practice test that are related but I am unsure about:

1. If an optimization problem can be solved using a greedy algorithm, 
there must be a solution for this optimization problem using dynamic programming as well.

2. If an optimization problem can be solved using dynamic programming, 
there must be a solution for this problem using a greedy algorithm as well.

I think the answers are 1. True and 2. False is this correct?

$\endgroup$
3
  • 2
    $\begingroup$ Does the course have any particular formal definition of "greedy algorithm" and "dynamic programming" in mind? $\endgroup$ Apr 7, 2014 at 1:50
  • $\begingroup$ What are your thoughts? What effort have you made on your own? What aspects of the question have you confused or uncertain about how to answer? Are there any aspects of dynamic programming and/or greedy programming that you are fuzzy about? $\endgroup$
    – D.W.
    Apr 7, 2014 at 6:53
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ Apr 7, 2014 at 16:19

1 Answer 1

2
$\begingroup$

Sounds about right, however informal the statement; dynamic programming is more powerful than greedy algorithms so if a problem should require it, a greedy algorithm won't be enough. And in the case in which a greedy algorithm can solve the problem, there will also be a correct dynamic programming solution since dynamic programming involves solving problems by optimizing overlapping subproblems. Suppose a greedy algorithm suffices, then the local optimal decision at each stage leads to the optimal solution and you can construct a dynamic programming solution to find the optimal solution. However, greedy algorithms are generally faster so if a problem can be solved with a greedy algorithm, it will typically be better to use.

$\endgroup$
4
  • $\begingroup$ Along the same lines I have the question True or False Dynamic programming requires that the optimization problem has a recursive solution? any input there? $\endgroup$
    – Deekor
    Apr 7, 2014 at 3:31
  • $\begingroup$ What do you mean by recursive solution? Referring to this other post on stackoverflow stackoverflow.com/questions/2093618/… you can reason that you will always be able to have an iterative solution in its place, unless you meant something slightly different. $\endgroup$ Apr 7, 2014 at 3:46
  • $\begingroup$ not really sure what he means, my professor wrote the question. $\endgroup$
    – Deekor
    Apr 7, 2014 at 3:55
  • 2
    $\begingroup$ Well, if a problem requires dynamic programming then its solution would be inductive in that you would have to solve the problem in terms of its subproblems; however, you would be able to express it iteratively, so recursion isn't required per se. $\endgroup$ Apr 7, 2014 at 3:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.