Design and Analysis of Algorithms

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