Sumanto's blog

Difference between Greedy and Constructive Algorithms?
By Sumanto, history, 4 years ago, In English

I searched on internet regarding this but didn't able to find perfect answer which could explain conceptually the difference between these two. Any light on this will help us all, i am sure many of would not know the theoretical difference between the two.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

To my understanding, greedy is an approach while constructive is a category.

For a very basic example, the solution to "What is the maximum sum of a subsequence of a given array $$$a$$$?" would be greedy, as one would greedily sum up all positive elements in $$$a$$$.

However, if the problem changes to "Output the subsequence of a given array $$$a$$$ that yields the maximum sum," the solution would have to construct the subsequence using a greedy approach.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    To me, a constructive problem is one in which you are asked to find an object satisfying certain constraints (in most cases it's obvious that solutions exist, or the problem will tell you), and the main part of the challenge is actually finding any of those solutions efficiently.

    A lot of people are using the term incorrectly recently, but I don't think asking to reconstruct the answer makes a problem constructive, even though the terms are similar. I would still classify your second example as greedy.

    Similarly, in lots of cases an explicit construction is used to prove that an answer is valid. I would still not classify those as constructive most of the time since usually by the time you figured out what it is you need to prove you've already done 90% of the work and finding the construction itself is relatively easy.

    In your example, if you have the greedy algorithm, finding an example subsequence is trivial, so it's a very small part of the problem. On the other hand, 418C - Square Table is very clearly constructive: there are lots of valid answers -- the main difficulty is finding a single example.

    Of course there are edge cases in which it's not so clear, but roughly it's determined by how long you take to construct an example versus how long you take to determine what it is that you should be trying to construct.

    → Reply