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?

  • 2
    $\begingroup$ Does the course have any particular formal definition of "greedy algorithm" and "dynamic programming" in mind? $\endgroup$ – Yuval Filmus Apr 7 '14 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 '14 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$ – David Richerby Apr 7 '14 at 16:19

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.

| cite | improve this answer | |
  • $\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 '14 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$ – Francesco Gramano Apr 7 '14 at 3:46
  • $\begingroup$ not really sure what he means, my professor wrote the question. $\endgroup$ – Deekor Apr 7 '14 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$ – Francesco Gramano Apr 7 '14 at 3:59

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