C++ Data Structures and Algorithm Design Principles

5. Greedy Algorithms

Learning Objectives

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.

Introduction

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, ...