5. Greedy Algorithms
By the end of this chapter, you will be able to:
- Describe the greedy approach to algorithm design
- Identify the optimal substructure and greedy choice properties of a problem
- Implement greedy algorithms such as fractional knapsack and greedy graph coloring
- Implement Kruskal's Minimum Spanning Tree algorithm using a disjoint-set data structure
In this chapter, we will look at various 'greedy' approaches to algorithm design and see how they can be applied in order to solve real-world problems.
In the previous chapter, we discussed the divide-and-conquer algorithm design technique, which solves a given problem by dividing the input into smaller subproblems, solving each subproblem, ...