O'Reilly logo

Design and Analysis of Algorithms by Himanshu B. Dave, Parag H. Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required