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 11

Abstract Algorithms 3—Dynamic Programming

Objectives

After reading this chapter, you should understand:

  • Dynamic Programming—principles and applications
  • Dynamic Programming—its power and limitations
  • The Principle of Optimality
  • Dynamic Programming and Greedy Strategies—Where to use what
  • Memoization
  • Significance of Optimal Substructure and Overlapping Sub-Problems
  • Shortest Path Algorithms—General Cases Dijkstra’s Algorithm, Bellman-Ford Algorithm, Floyd-Warshall Algorithm
  • Maximum Flow Problems: Ford-Fulkerson Method

Chapter Outline

11.1 Introduction

11.2 Example—Multistage Graphs

11.3 Example—Traveling Salesman

11.4 Example—Matrix Multiplication

11.4.1 Brute Force Solution—Try all Possible Parenthesisations

11.4.2 Dynamic Programming ...

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