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 by Pearson now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial