Chapter 6: Dynamic Programming

Dynamic programming is a combination of divide and conquer and brute-force strategies: it (implicitly) looks at all possible solutions by decomposing problems into smaller ones, and it subtly takes advantage of things it knows to pick the best solution without explicitly looking at each one. The authors liken it to a balancing act that takes time to become comfortable with. Dynamic Programming is the antithesis of the greedy strategy because it doesn't attempt to build up the solution at every step. Often it is more powerful than the other techniques we've learned. As usual, we start with an example rather than with an attempt to define the abstract strategy.

I learned a new word: “nondecreasing” (and I like it, since it takes care of those flat slopes which “increasing” fails hard at). Anyway, in this problem, the requests are ordered according to finish time, with the latest finish times at the end. The crucial idea behind this problem is: either the optimal solutions includes the last request, j, or it doesn't. This means the optimal solution can be expressed as the choice between including that request (thus adding the value of that request to the total and dealing with the remaining requests compatible with j) and not including it (finding the optimal solution of the first j-1 requests).

(6.1) OPT(j) = max(Vj + OPT(p(j)), OPT(j-1))

This is a recursive process that is hard to visualize at first. The initial problem with designing an algorithm is that is seems to require an exponential number of recursive calls (but does it really?!). Nah, we should realize that there are only ~n problems that need to be solved. Just like with Fibonacci, we don't need to compute F(2) a million times. We can compute it only once and record its value in an easy-to-access array. This is the idea behind memoization. With the weighed interval schedule problem, a memoized array allows the algorithm to make O(n) recursive calls, rather than an exponential number of them.

(6.5) Given the array M of the optimal values of the sub-problems, Find-Solution returns an optimal solution in O(n) time.

Recap/basics of dynamic programming: In the WIS problem, converted an exponential-time recursive algorithm to a polynomial-time recursive algorithm by memoization. Realize that recursion is not necessary; an iterative algorithm to compute M is all we need, since once we have M, we have the solution. Start at M[0] and iterate through M until M is full. At each stage, it should write OPT(j) to M(j).* The running time of the iterative algorithm is O(n), as long as the principles hold.

Basic principles (p. 260):

• (i) There are only a polynomial number of subproblems.
• (ii) The solution to the original problem can be easily computed from the solutions to the subproblems.
• (iii) There is a natural ordering on subproblems from “smallest” to “largest,” together with an easy-to-compute recurrence that allows one to determine the solution to a subproblem from the solutions to some number of smaller subproblems.

* There is a good picture that displays this (Figure 6.5, p. 260).

Problem: partition a set of points into some number of segments. Drawing n-1 segments (one segment between every two points) is not always optimal, since each line segment has a cost (and sometimes graphs are linear enough to warrant longer segments).

Goal: minimize the sum of squared errors at each point plus the cost of creating x line segments.

We know the last point (j) is the endpoint of a segment whose starting point is somewhere earlier (i). This means the optimal partition for all of the points (1 through j) can be written as OPT(j) = squared_error_cost(i,j) + C + OPT(i-1).

This leads to (6.7) and from that we can come up with an algorithm.

The knapsack problem requires us to think about the remaining weight in the knapsack. This is why its subproblems require two parameters instead of just one (if an item is added to the knapsack, then we must subtract that object's weight from the total available weight for the knapsack). We memoize this information in an n-by-W array which we can fill up in O(nW) time.

Problem outline: Knowing secondary structures is useful. There are basic rules that govern RNA base pairing. We think nature produces secondary structures that have the maximum number of base pairs. Therefore, to predict secondary structure, we want an algorithm that takes as input the RNA-bases and outputs the secondary structure that maximizes the number of base pairs for that set.

Solution outline: The recurrence is different from others we've seen. One rule is that bases in a base pair must be separated by at least 4 other bases. Therefore the solution for any number of bases less than 6 is the empty set. For j greater than 5, we notice that base j is either in a pairing or it isn't. But we cannot phrase our recurrence only in terms of j. (OPT(j) won't work.) We need to include another variable i because of the crossing condition (another pairing rule). We need to know the first and last bases that are possible for a pairing. But it is not always the case that base 1 is the first base that could possibly be included in a pairing. Sometimes bases are out of the question. Therefore the recurrence looks like this instead:

(6.13) OPT(i,j) = max(OPT(i,j-1), max(1 + OPT(i,t-1) + OPT(t+1,j-1)

See Figure 6.16 for an illustration of building up the subproblems. The solution we want is OPT(1,n). The running time of the algorithm is bounded by O(n^3).

Problem outline: Need a measure by which to compare strings for similarity. Must “define the notion of similarity between two strings” (K&T, 279). Search engine queries, computational biology are applications of sequence alignment.

Solution outline: Find a minimum-cost alignment between the two strings. Alignments are composed of gaps and mismatches. The total cost of all gaps and mismatches is a measure of how dissimilar two strings are. So to see how similar two strings are, we need the minimum-cost alignment between them. We do this with the following recurrence relation:

(6.16) OPT(i,j) = min(mismatch_cost(xi,yi) + OPT(i-1,j-1), gap_cost + OPT(i-1,j), gap_cost + OPT(i,j-1))

This is because there are three possibilities for the mth letter in string 1 and the nth letter in string 2: they form a pair in the optimal alignment, the mth letter in string 1 is not in any pair in the optimal alignment, or the nth letter in string 2 is not in any pair in the optimal alignment. The dynamically programmed algorithm for this problem runs in O(mn) time because every pair (i,j) must be considered from 1…m and 1…n, and each of these takes at most constant time. It also takes O(mn) space.

This section shows us an improved algorithm for sequence alignment. It still runs in O(mn) time but it decreases the space requirement from O(mn) to O(m+n). We realize that computing a single column in the memoized array in the last problem only requires us to know about the current column and the previous column. Therefore it is possible to arrive at the solution while only maintaining a m-by-2 array instead of a m-by-n array. This idea will work nicely for building up to the solution value (i.e., the total cost of all gaps and mismatches)… but we also want to know the optimal sequence itself.

We do this by incorporating divide-and-conquer principles into our algorithm. I'm slightly confused by the divide-and-conquer component to this problem. In class we did it with the graph in Figure 6.19. We started in the top left and found the shortest path to some midpoint, then we did the same thing from the bottom right. I will need to look in more depth at the pseudo-code on page 288 to get a better grasp of the concept.

Problem outline: We want to find the shortest path between two nodes in a directed graph. We cannot use Dijkstra's Algorithm because there can be negative weights. (We won't know whether we have grown the blob in the right way because there could be a negative edge in the future that provides a shorter path to some node already in the blob.) Therefore we want to build up partial solutions. The first partial solution is the cost of s→t that uses at most one edge; if s doesn't have an edge to t, then the value we put in the memoized array is infinity. (6.22) says that the longest possible optimal path has n-1 edges. So at most we would do n-1 iterations of this.

Here we assume no negative cycles because otherwise the optimal path would follow that cycle infinitely many times and so reduce the cost of the path to negative infinity. But that would be stupid. We saw from class that like the problem above we can fill any column by referring only to the column itself and the column that came before it.

(6.25) says that the shortest path algorithm can run in O(mn) time.

Outline: An instance of the shortest-path problem on an undirected graph for which all edge costs are positive. Dijkstra's is possible, but we don't want to use it (we can think of something better) because we are talking about routers here and we prefer to work with local information. The BF Algorithm from 6.8 has a local property that can be utilized in a dynamic programming solution. If we maintained each node's value in a memoized array, we could update it by simply looking at the values of all of its neighbors and computing the total cost of that value and an edge to that node. This section proposes a change in the BF Algorithm from a “pull-based” implementation to a “push-based” implementation: this means we will only update the values in the memoized array for nodes that have been affected by a recent change, saving a lot of computation time.

Problems: Assumes edge costs will remain constant during runtime, which for many reasons will probably not be the case in practice. Also, there is the potential “problem of counting to infinity” which we talked about in class - two nodes constantly update one another and tell the other that they have been updated, which leads to an infinite number of operations.