Chapter 6: Dynamic Programming

The basic idea behind dynamic programming is similar to that of divide and conquer and opposite to that of greedy: dynamic programming divides the problem into subproblems and then takes the solutions to those to create the solution to the larger problem. This leads us to think that the dynamic programming approach may reach up to the brute force search time, however we will never actually need to examine every solution to our problem explicitly.

First, some notation to assist discussion. We will call p(j) the largest index i<j such that i and j are disjoint. This is to say that i is the leftmost interval that ends before j begins. We can also consider an optimal scheduling, the precise contents of which are unknown, that we will call O. We know that no interval between p(n) and n can be included in O if n is included in O because they overlap n. Additionally, O including n also includes an optimal solution for intervals {1,…,p(n)} because if it did not we could simply replace whatever solution was there with that optimal solution without fearing a loss of optimality or overlapping n.

Using that principle we can develop the statement that a an interval j should only be added to the solution if the sum of it and its optimal solution for p(j) is greater than the optimal solution of j-1. This statement obviously lends itself to recursion, since one must calculate the optimal set of intervals for p(j) and for j-1. Another thing that is easy to see from this includes the algorithm's possible invocation of redundant recursive calls.

The redundant recursive calling can be solved by memoization, which creates an array M that stores the results of the function's calling on j in case it is called on j again. The memoization array helps the algorithm to run in linear time instead of exponential. Somehow this also helps the algorithm to return to solution, in addition to its value, in linear time. I think it may take the solution with the optimal size from M and return that and the solution that it calculates but I can not tell for sure.

The iterative version of the algorithm works by directly computing the entries in M rather than relying on the memoized recursion present in the recursive version. This algorithm works by iterating though the n items and computing each ones value, which is then stored directly in the array. It is easy to see that the algorithm then has linear running time since it will execute a constant time operation on each of its n passes through the loop.

From here we are able to develop an outline of dynamic programming. There are three properties that should be true of a problem in order to guide or development of a dynamic programming approach to solving the problem. First, there must be only a polynomial number of subproblems. Additionally, the solution to the original problem should be easy to arrive at from the solutions to the subproblems. Finally, there should be an ordering to the subproblems which allows the solution of some subproblems to be computed from the solutions of other subproblems.

Sometimes, it can be a challenge to determine whether it is more useful to first reason about the structure of the optimal solution or whether it is more useful to come up with subproblems that seem natural and then figuring a recurrence which links them. In this way, dynamic programming can be reminiscent of a chicken-and-the egg reasoning puzzle.

What we will call the error of a line of best fit is the sum of each point's distance from the line. It is relatively easy to place such a line and calculate its error when all the points seem to fit around one line, but sometimes the points in a data set can look like they fit on a sequence of two or more lines. This makes us want to find a way to allow the algorithm to fit a set of lines to the data points. We cannot allow it to fit an arbitrarily large set of lines, because then our error will be 0. We also cannot hard-code in any number of lines because the points could better fit on a different number of lines.

This dilemma leads us to explore the issue of change detection, which is helps us identify a few points at which a change occurs. Such a technique will help to tell us how many linear approximations to use. To assist us in the solving of this problem we will define a penalty of a partition as the sum of the number of segments times a given multiplier and the error of the optimal line through a segment of points. We want to minimize the penalty. As we increase the number of segments into which the data is partitioned, we decrease the error of each segment but increase the penalty in terms of number of segments.

To design the algorithm, we can begin by thinking that the final point in the set of points will only be in one segment and that segment must begin at a point. If we can figure out what these two points are, then we will have found the composition of the final segment and we can remove those points from the data. Letting e_{i, n} be the error for this last segment, we can say that the optimal solution for n^th point is the error of segment i to n plus our penalty for adding a new segment plus the optimal solution for all the points up to point i.

To be completely honest, I am not completely sure what statement 6.7 in the book is saying, so I will look back over that at a later time..

The algorithm uses O(n³) time to calculate the error for each pair of points, however once this is calculated it runs in O(N²) time.