Introduction to Algorithms, Third Edition

Part IV
Advanced Design and Analysis Techniques
matroid theory, which provides a mathematical basis that can help us to show that
a greedy algorithm yields an optimal solution.
We use amortized analysis to analyze certain algorithms that perform a sequence
of similar operations. Instead of bounding the cost of the sequence of operations
by bounding the actual cost of each operation separately, an amortized analysis
provides a bound on the actual cost of the entire sequence. One advantage of this
approach is that although some operations might be expensive, many others might
be cheap. In other words, many of the operations might run in well under the worst-
case time. Amortized analysis is not just an analysis tool, however; it is also a way
of thinking about the design of algorithms, since the design of an algorithm and the
analysis of its running time are often closely intertwined. Chapter 17 introduces
three ways to perform an amortized analysis of an algorithm.

---

15
Dynamic Programming
Dynamic programming, like the divide-and-conquer method, solves problems by
combining the solutions to subproblems. (“Programming” in this context refers
to a tabular method, not to writing computer code.) As we saw in Chapters 2
and 4, divide-and-conquer algorithms partition the problem into disjoint subprob-
lems, solve the subproblems recursively, and then combine their solutions to solve
the original problem. In contrast, dynamic programming applies when the subprob-
lems overlap—that is, when subproblems share subsubproblems. In this context,
a divide-and-conquer algorithm does more work than necessary, repeatedly solv-
ing the common subsubproblems. A dynamic-programming algorithm solves each
subsubproblem just once and then saves its answer in a table, thereby avoiding the
work of recomputing the answer every time it solves each subsubproblem.
We typically apply dynamic programming to