how to decide which algorithm technique to follow?

can somebody help me to know that how do we decide the algorithm technique to be used ? like i should apply greedy approach to a problem or DP or divide and conquer.

or i should always try greedy and if it is giving WA then apply DP?

Thanks in advance :slight_smile:

1 Like

@hitesh_noty:

you cannot depend on greedy solutions always, the setters always set the problem in such way that the problem is a implemntation of a single or multiple concepts in a program. The timelimits are set based on the time taken to solve using that concept.(also border or boundary cases are not be forgetten when speaking about WA ;))

So, one can only pass the timelimit if the complexity of his solution is similar or better than that of setter.

The following link has a list of must known algorithms provided by user tyrant.

Happy JAN14 :slight_smile:

@hitesh_noty >> I think you should first understand greedy algorithms and dynamic programming algorithms properly. E.g from video lectures. There are few parameters for which a DP solution can be applied.
There is a term called correctness of an algorithm, which forces you to think backwards and later you can find out real quick about what to choose greedy or DP.

Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step (Cormen et al. pp. 381–2). Otherwise, providing the problem exhibits overlapping subproblems as well, dynamic programming is used.

Conclusion: Read and practice!

but those concepts also have those approaches…like one follow’s greedy and other follows dp or whatever. my question was how to choose between those… how do i get to know that which approach to be followed for “simple problems” should i always try greedy first?

@hitesh_noty: greedy is worth a try when u are not sure about what approach to take.

but how can we be sure…i mean programmers normally don’t try greedy first always. how to judge that?
is it guessed by looking at time limit?

“to know the optimal approach for a problem” can be done only through PRACTICE!!!