Design and Analysis of Algorithms

Chapter 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 A lgorithms (Dijkstra’s)

Chapter Outline

10.1 Introduction

10.2 Example Knapsack Problem

10.3 Job Sequencing with Deadlines

10.4 Example—Minimum Spanning Trees

10.4.1 Prim ’s Algorithm

10.4.2 Kruskal ’s A lgorithm

10.4.3 1st version—Kruskal. c

10.4.4 ...