4.0 Greedy Algorithms

An algorithm is greedy if it builds up a solution in small steps, choosing the best solution at step to optimize some underlying criterion. It often is possible to find many greedy solutions for the same problem. The biggest challenge when dealing with greedy algorithms is to find the cases in which the found greedy algorithms work well and prove that they indeed work well. The main approaches used are:

• The exchange argument: consider any possible solution to the problem and gradually transform it into a solution found by the greedy algorithm without altering the solution's quality.
• The greedy stays ahead: Measure the greedy solution's progress in a step-by-step fashion and show that it does better than any algorithm at each step.

Greedy algorithms are very useful as they arise in problems as varied as finding shortest path in a graph, network routing, interval scheduling,etc,…

This was just an introduction,it was short and concise, so I give it an 8/10 for a well organized introduction.