Design and analysis of Algorithms, 2nd Edition

10

Abstract Algorithms 2—Greedy Methods

Objectives

After reading this chapter, you should understand:

• Greedy Strategy: Principles through examples
• The terms: Objective functions, Optimality and Feasibility
• Applicability and limitations of Greedy strategy
• How choice of complex data structures influences algorithm complexity
• The Union-Find Data Structure
• Matroids: Properties and Applications
• Minimum Spanning Tree Algorithms (Kruskal’s, Prims’s): Correctness and Efficiency
• Shortest Path Algorithms (Dijkstra’s)

Computers make it easier to do a lot of things, but most of the things they make it easier to do don’t need to be done.

—Andy Rooney

To understand that cleverness can lead to stupidity is to be close to the ways of Heaven.

—Huang ...