Lesson plan
greedy algorithm
A greedy algorithm is an algorithm which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices. Greedy algorithms are often used to solve combinatorial optimization problems. If an optimization problem only depends on the partial solution of solving it for one subproblem, we can solve this problem by "greedily" considering only the locally optimal subproblem. In this sense, a greedy algorithm is a special case of a dynamic programming algorithm. Uriel Feige notes that: [Greedy algorithms] may be viewed as the ultimate form of dynamic programming, in which only one partial solution is maintained. The problem needs to have much more structure for this approach to work. In many cases, a greedy algorithm does not produce an exact solution, but can yield solutions that approximate an exact solution in a reasonable amount of time. An example of a problem which admits an exact greedy solution, the activity selection problem. Given a collection of tasks which can be done between allotted time intervals, the problem is to determine the maximum number of tasks that can be done. A greedy algorithm in O(n\log(n)) which solves this problem sorts the tasks by the end time and then repeatedly chooses the first task that begins after the last task ended.…
Article summary
A greedy algorithm is an algorithm which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices. Greedy algorithms are often used to solve combinatorial optimization problems. If an optimization problem only depends on the partial solution of solving it for one subproblem, we can solve this problem by "greedily" considering only the locally optimal subproblem. In this sense, a greedy algorithm is a special case of a dynamic programming algorithm. Uriel Feige notes that: [Greedy algorithms] may be viewed as the ultimate form of dynamic programming, in which only one partial solution is maintained. The problem needs to have much more structure for this approach to work. In many cases, a greedy algorithm does not produce an exact solution, but can yield solutions that approximate an exact solution in a reasonable amount of time. An example of a problem which admits an exact greedy solution, the activity selection problem. Given a collection of tasks which can be done between allotted time intervals, the problem is to determine the maximum number of tasks that can be done. A greedy algorithm in O(n\log(n)) which solves this problem sorts the tasks by the end time and then repeatedly chooses the first task that begins after the last task ended.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.