Greedy vs Dynamic Programming

Revision en2, by IvayloS, 2015-09-24 15:04:23

It so happens that apart from being an active member on Code forces I spend quite some time on stackoverflow.com trying to provide help for users around the world. Every now and then I see a question where the most upvoted and accepted answer is not entirely correct but this time it is a bit different. Take a look at this question: http://stackoverflow.com/q/13713572/812912 The discussion is pretty much on what is greedy and DP and isn't one of them a subset of the other. The most upvoted and accepted answer states the following:

The difference between dynamic programming and greedy algorithms is that with dynamic programming, the subproblems overlap.

(take a look at the whole answer here)

In fact the whole answer is quite interesting. I tried to start a discussion with the poster, explaining what is wrong but I keep getting more and more interesting statements. Here is an example(in the comments section):

@IvayloStrandjev: No, Dijkstra's without the heap would be a greedy algorithm. The heap introduces a dependency whereby when a decision is made about a solution to a subproblem (the shortest path to a vertex) is used to facilitate the decisions to the other subproblems. This is why Dijkstra's is not simply a greedy algorithm (or else you would have to make the decisions independently). This agrees with the top Quora answer. –  Neil G Sep 18 at 13:54

If also read through the chat you will notice that the same user claims that computing the n-th Fibonacci number using memoization is DP(which is correct), but without memoization it would be greedy(which is nonsense).

It is first time I see an accepted answer that is so off target and where the poster ignores any reasoning. Truth is that this case annoys me quite a lot — I see something that is totally incorrect and yet it seems to be accepted by the community. More people would read this answer and most will believe it is correct. Thus I am turning to code forces community for some support. Apparently my opinion is not authoritative enough and the links I provide are not enough. I would also like to hear what you think on the whole discussion.

Tags stackoverflow, greedy, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English IvayloS 2015-09-24 15:11:10 4 Tiny change: '~~~\n\nIf also read' -> '~~~\n\nIf you also read'
en2 English IvayloS 2015-09-24 15:04:23 8 Tiny change: 'zation is greedy(which is ' -> 'zation is DP(which is '
en1 English IvayloS 2015-09-24 14:48:56 2254 Initial revision (published)