Chapter 5: Dynamic Programming

A different version of the previously-discussed interval scheduling problem is one in which each interval has a certain value/weight and we want to find a maximum value. There is no natural greedy algorithm which we know to be able to solve this problem, so we must use dynamic programming with recursion. We would like to assume that the intervals are sorted by their finishing time. We then start by considering an optimal solution O, though we don't know what the solution is. We do know that the last interval, n, is either in O or is not, obviously. We can then look recursively at the smaller solutions that result from this basic fact by looking at what we know about the solution in the case in which n is in O and the case in which it's not. A crucial component of dynamic programming is stated as follows: a dynamic programming solution is based [on] a recurrence equation that expresses the optimal solution (or its value) in terms of the optimal solutions to smaller subproblems.

If we have sorted the values in order of finishing time and have computed p(j), the largest index i < j such that intervals i and j are disjoint, for each j, then we have an algorithm to find OPT(n):

  Compute-Opt(j)
      If j = 0 then
          Return 0
      Else
          Return max(Vj + Compute-Opt(p(j)), Compute-Opt(j - 1))
      Endif

This algorithm correctly computes OPT(j) for each j = 1, 2, …, n. The main problem with this algorithm is that it will run exponentially. To solve this we will use memoization. Memoization is the technique of saving values that have already been computed, and it helps eliminate redundancy and reduce running time. Here is a better algorithm, which uses memoization:

  M-Compute-Opt(j)
      If j = 0 then
          Return 0
      Else if M[j] is not empty then
          Return M[j]
      Else
          Define M[j] = max(Vj + M-Compute-Opt(p(j)), M-Compute-Opt(j - 1))
          Return M[j]
      Endif

The running time of this algorithm is O(n), which is much preferred to the previous, non-memoized version. It is also possible to make a few small changes to this algorithm to compute the solution, not just the max value. I think this section was a necessary addition to our class discussion of this topic, which was a little confusing. I am still a little confused about the second if statement but overall I understand. I rate it an 8.

A different way to use dynamic problem is to iterate over subproblems rather that compute solutions recursively. In this new algorithm (used to solve the same problem as in section 6.1) we have an array M and defines the value M[j] as in 6.1. Then, M[n] is the value of the optimal solution. Here is the iterative algorithm to compute this solution:

  Iterative-Compute-Opt
      M[0] = 0
      For j = 1, 2, ..., n
          M[j] = max(Vj + M[p(j)], M[j - 1])
      Endfor

Typically, iterative algorithms are used since they are easier to express. For every memoized recursive algorithm there is an equivalent iterative algorithm, and vice-versa. To develop an algorithm based on dynamic programming, we need a collection of subproblems from an original problem which satisfies the following:

  i.) there are only a polynomial number of solutions
  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 "largest" to "smallest," 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.

This section made a good amount of sense because the explanation is class was fairly thorough. I still am a little confused by how the array M can really solve the problem in such simplistic lines of code. I rate it a 7.

A different kind of problem involves “multi-way choices,” where at each step, we have a polynomial number of possibilities to consider for the structure of our optimal solution. The problem we will look at to illustrate this is one where we are given a set of points and would like to find lines of best fit which minimize error. This idea gives us the Segmented Least Squares Problem: we want to fit the points well (minimize error) using as few lines as possible. For the algorithm, we need to define the following recurrence: For the subproblem on the points p₁, …, p_j, OPT(j) = min (from 1 to j inclusive) of e_i,j + C + OPT(i - 1) and the segment p_i,…, p_j is used in an optimum solution for the subproblem if and only if the minimum is obtained using index i. Here is the algorithm:

  Segmented-Least-Squares(n)
      Array M[0...n]
      Set M[0] = 0
      For all pairs i ≤ j 
          Compute the least squares error e(i,j) for the segment Pi, ..., Pj
      Endfor
      For j = 1, 2, ..., n
          Use the recurrence above to compute M[j]
      Endfor
      Return M[n]

As with weighted interval scheduling, we can easily create an algorithm using M to find what the segments are. The total time to compute all e_i,j is O(n³) and once these have all been computed the algorithm is O(n²) running time. The way the book explained this seems extremely different from what we discussed in class so I am very confused. I do not really understand the recurrence perhaps. I rate my understanding a 5.