This chapter is about dynamic programming, which is a more powerful approach than greedy or divide and conquer methods. The basic idea is kind of the opposite of greedy approach. You explore all possible solutions to a problem but breaking a problem up into subproblems, the building up the correct solution into larger subproblems. This may seem to be close to brute-force, but it is not because of the way it explores the possible solutions. It never explicitly looks at every solution, but carefully breaks it down so that we can find an optimal solution with a good running time.

This problem is an extension of the interval scheduling problem that we developed a greedy solution for previously. The difference is that each interval has a weight/value and we want to maximize the value of the accepted set of intervals. There is no greedy solution to this problem, but we can set it up similarly, with the n jobs ordered by finish time. For each job j, we define p(j) which is the largest interval that is compatible(i.e., disjoint) with j. To start considering our optimal solution, we know that job n is either in the optimal solution, or not in the optimal solution. If it is, then the optimal solution is now the value of n plus the opt(p(n)). If n is not in the optimal solution, then the optimal solution is opt(n-1). This intuitively develops into a recursive algorithm.

However, the running time is bad because the recursive calls lead to a lot of redundancy in computing the various optimal solutions. The fix to this problem is to use memoization, which is the process of storing the value of each optimal subproblem the first time we compute in and then just looking it up later. We can implement this process in O(n) time and then build up the set of intervals in the optimal solution from the array values of solutions for subproblems already computed. The algorithms are on pages 256-258. This process is confusing at first, but makes more sense as we go through it. It is actually pretty intuitive and very useful.

This section presents a slightly different solution to the Weighted Interval Problem that will then act as a template for future dynamic programming problems. This solution is iterative and gets rid of the need for the memoized recursion. The important aspect of the previous algorithm is the array M of the values of the solutions to the subproblems. We can actually compute the values of M using a iterative approach instead of a recursive one. By starting at the beginning of M and incrementing j, we can easily compute M[j] using the maximum of the opt(j-1) and the value of j plus opt(p(j)), as done in section 6.1. I think the book didn't do a great job of explaining this iterative approach, but it made sense in class, so it was ok.

In general, we make dynamic programming algorithms using the iterative approach rather than the recursive memoization one. The iterative solution to the Weighted Interval Scheduling Problem leads to a rough template for dynamic programming algorithms. Basically, you need to be able to find a polynomial number of subproblems such that you can easily get the overall solution from the solutions to the subproblems and there is some natural of intuitive ordering of the subproblems (i.e., smallest to largest) with an easy recurrence. It is often good to consider the recurrence by thinking about what the optimal solution would like before determining the subproblems.

This problem is derived from the process of finding a line of best fit for a set of points. A line of best fit is not always helpful if you have a set of points that curves in such a way that it looks like 2 or more lines would be needed to make the error small. In this case, we consider the problem of finding a set of lines that gives us the best fit. In order to avoid the trivial solution (where you would have n-1 lines that connect 2 points each), we create a penalty for each partition which is the number of segments times a constant C plus the error value. Thus, our goals is to find the partition with the minimum penalty.

The key point to this problem is to observe that the last point, call it n, belongs in only one segment of the optimal partition and that segment begins at some earlier point, i. We can say that the value of the optimal solution for the last segment from i to n is e(i,n) + C + opt(i-1), where e is the error. The optimal solution for each subproblem can be achieved by taking the minimum of these solutions for combinations of i and j. The algorithm is on page 265. Similarly to the weighted interval problem, we can trace back through the array to get the set of lines in opt(n). This algorithm runs in O(n^2) time. I think this algorithm is kind of hard to come up with on my own, but by looking at the similarities to the weighted interval problem, it is getting easier to see and understand the general approach for dynamic programming algorithms.

The Subset Sums Problem is when we have n requests, a bound W, and weights w(i) and we need to select the subset of items that gives us the largest weight subject to the bound W. Like any dynamic programming problem so far, we need to find small subproblems that can then make the original solution easier to find. The subproblems we used for the weighted interval scheduling problem will not work in this case - we actually need more subproblems. We need a subproblem for for each item i and each possible value for the remaining weight. Basically we are saying if W < w(i) then opt(i,w) = opt(i-1,W). Otherwise, opt(i,W) = maximum of opt(i-1,W) and w(i) + opt(i-1, W-w(i)). The second part is when item i is in the subset. The algorithm is on page 269, It uses a 2-dimensional array as an extension of previous problems and runs in O(nW), or pseudo-polynomial time.

The Knapsack Problem is an extension where each item i has a weight and a value, and there is a maximum weight for the knapsack. The idea is to maximize the total value you can put in the knapsack, subject to the weight constraint. The recurrence is the same as the Subset Sums Problem, and it also runs in O(nW) time.

This section discusses a problem where is not easy or possible to naturally break the problem into subproblems. The problem here is looking at RNA strands. An RNA strand consists of a sequence of the symbols {A,C,G,U} where A,U and G,C can pair up. The secondary structure is when the strand wraps around and pairs up with itself, which some restrictions. Each pair must be separated by 4 bases (i.e. i <j-4), each base can only pair up once (and with the corresponding base only), and the strand cannot cross itself. The goal is to maximize the number of base pairs for a strand, which corresponds to the optimizing the total free energy of the molecule.

Because of the no crossing rule, we cannot look at the recurrence the way we have in the past. Instead we have to add a variable, so OPT(i,j) is the maximum number of base pairs in the secondary structure from i to j. We get the two subproblems where either j does not pair up, or j does pair, in which case we have to look at two more subproblems. If j pairs with t, for some t < j-4, then we have to look at pairing from i to t-1 and pairings from t+1 to j. The optimal solution is on page 276 and the algorithm is on page 277. The running time of this algorithm is O(n^3) because there are O(n^2) subproblems which each take O(n) to evaluate.

Sequence Alignment is the idea of looking at how similar two string are, and comes up in internet searches and dictionaries, in addition to computational biology applications. When aligning two words, you look at gaps and mismatches, which means there are several ways to align two words or strings. The goal is to minimize the differences between the strings if given costs/weights for gaps and mismatches. To set up the problem, let δ be the gap penalty and let α be the mismatch cost (α = 0 if the characters are the same). M is the sum of these and we want to minimize M.

In the optimal alignment M of strings X and Y, there are three possibilities. Either (m,n) is in M, or m in X is not matched or n in Y is not matched. If the first case is true, then opt(m,n) = α + opt(m-1,n-1). The m not matched case gives us opt(m,n) = δ + opt(m-1, n) and the n not matched case gives us opt(m,n) = δ + opt(m, n-1). We naturally want the minimum of these three cases. There are O(mn) entries in the array so the running time is O(mn). It may also be helpful to visualize this problem as a graph of i by j nodes with the edges between all adjacent nodes. The gap penalty is the cost of the horizontal and vertical edges and the mismatch cost for (i,j) is the diagonal edge. The value of the optimal alignment is the length of the shortest path from (0,0) to (m,n). This is a clever way of looking at it that I would not have thought of. I like looking at things as graphs, but it is easier to see the dynamic programming and recurrence relation the other way.

This section looks at reducing the O(mn) space bound on sequence alignment because in biology applications, we could compare string of 100,000 characters each. Therefore, we can improve the algorithm to only require O(m+n) space. We can do this by using an idea from divide-and-conquer. We can divide the problem into recursive calls so we can reuse the computation. The key observation is that we don't the whole array; instead we can just keep the current and previous columns of the array. The algorithm for this enhanced algorithm is on page 285. At the completion of the algorithm, the array at [i,1] hold opt(i,n). The problem is then finding the alignment itself, not just the value.

This is where the graph representation of sequence alignment comes in handy. Let f(i,j) be the shortest path through the graph from (0,0) to (i,j) and let g(i,j) be the shortest path from (i,j) to (m,n). g is still a dynamic programming approach but built up in reverse. Now, since we have forward and backward formulations, we can combine then to get the total optimal solution. Using divide-and-conquer techniques, we can divide G and compute f(i, n/2) and g(i, n/2) and determine the shortest path recursively. The algorithm to find the alignment is on page 288. It uses O(m+n) space, as we wanted, and the running time remains O(mn).

This section discusses the shortest path problem that allows negative weights on edges. Previously we used Dijkstra's Algorithm to solve this problem for positive weights. Our new algorithm is more flexible and applicable than Dijkstra's Algorithm. For this problem, it is important that there be no cycles of negative cost in the graph because this would mean we could build increasingly negative paths by going around the cycle multiple times. Dijkstra's Algorithm does not work with negative weights because expensive edges can be compensated by negative edges, which will not be produced by a greedy algorithm. Adding a constant to make all edges positive also does not work due to the lengths of various paths.

Our dynamic programming solution is based on the fact that for a graph with no negative cycles, the shortest path has at most n-1 edges, so our optimal solution is opt(i, v). So either the path contains the i-1 edges, in which case opt(i,v) = opt(i-1,v) or the path contains i edges and the first edge is (v,w), in which case opt(i,v) = cost(v,w) + opt(i-1,w). The total solution in opt(n-1,s). The algorithm is given on page 294 and runs in O(n^3) time. We can reduce the running time to O(mn) because, while the graph could have up to n^2 edges, most graphs are much sparser. The space requirement can also be reduced to linear by only keeping track of one value for each node, the length of the shortest path so far, and updating it as we go. Because of less space we have to keep track of each node's first node (after itself) in order to be able to trace the solution back.

A common application of the Shortest Path Problem is routers in a communication network. If the costs on edges represent the delay on a link between two nodes, you can find the minimum delay from s to t. It is possible to make this work by running a protocol to gather global information, but it is better if we can make an algorithm that only needs the information form its neighbors. To update M[v], we only need to know M[w] of its neighbor w. We can potentially terminate the algorithm early because we are only updating values if their neighbor changes, so if no values change, we are done.

This algorithm is good because it can update at any time and still run, since it does not need all the information from the beginning. If we maintain distances between all nodes, the algorithm is known as a distance vector protocol. The potential problem here is that it comes from a dynamic programming idea that assumes costs are constant. However, edges costs can change, or even be deleted. If this is the case, it can run into a “counting to infinity” problem. This is solved with path vector protocols, which keep track of some representation of the whole path.