CS502 Fundamentals of Algorithms GDB No.1 Solution Fall Semester 2013

[Vuhelper]

Idea Solution

Greedy algorithms with optimization problems
Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems
What kinds of optimization problems can be solved by greedy algorithms accurately?
Greedy algorithms can be characterized as being 'short sighted', and as 'non-recoverable'. They are ideal only for problems which have 'optimal substructure'.
Optimal substructure means that optimising every part of the structure will give an optimal solution for the whole structure.