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

A computer is essentially a trained squirrel: acting on reflex, thoughtlessly running back and forth and storing away nuts until some other stimulus makes it do somthing else.

—Ted Nelson

Nature laughs at the difficulties of ...

Get Design and analysis of Algorithms, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.