Posts: 9,583
Threads: 8,089
Joined: Apr 2011
CS502 Fundamentals of Algorithms GDB No.1 Solution Fall Semester 2013
Graded Discussion Board
Dear Students!
Graded Discussion Board (GDB) will be launched on Feb 11, 2013 and it will remain open till Feb 12, 2013.
Topic:
A “greedy algorithm” always works well for optimization problems. Support or contradict this statement with solid arguments.
Note:
A concise, coherent and to the point comment is preferred over lengthy comment having irrelevant details. Your comment must not be more than 5-7 lines. Comments, posted on regular Lesson's MDB or sent through email will NOT be considered. Any request about such an acceptance will not be catered.
Posts: 9,583
Threads: 8,089
Joined: Apr 2011
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.
mileys81:[SIZE="4"][SIZE="3"]....[/SIZE][/SIZE]