Chapter 6

The problem is similar to our previous Interval Scheduling problem with the added case that jobs now have different weights; thus, no greedy algorithm can be used to solve this problem, so we must switch to dynamic programming. More specifically, we use a recursive algorithm. The algorithm relies on a simple observation: for any job j, we wither pick j or we do not pick j. This observation helps formulate the recursive case:

   Compute-Opt(j):
   if j = 0
      return 0
   elif M[j] is not empty
      return M[j]
   else
      M[j] = max(vj + Compute-Opt(p(j)), Compute-Opt(j-1))

In the recursive case, we take the maximum of the solution containing j and the solution not containing j (picking job j or not picking job j). The runtime of this algorithm is O(n) since it makes use of memoization. Computed values are stored in array M and recalled when needed, eliminating redundant computations. Lastly, we construct a second algorithm that returns the actual set of jobs that Compute-Opt would choose since Compute-Opt only returns the value of the optimal solution. This algorithm also runs in O(n) time. The readability of this section is 8/10.

The Weighted Interval Scheduling problem can also be solved using an iterative algorithm as opposed to a recursive one. Both algorithms are dynamic and use memoization.

   Iterative-Compute-Opt(j):
      M[0] = 0
      for j-1 to n
         M[j] = max(vj + M[p(j)], M[j-1])
         

The iterative algorithm also has a runtime of O(n). Both algorithms are dynamic because the divide the main problem into subproblems and then combine computed subproblems to solve the overall problem. The readability of this sections is 8/10.

The problem arises out of best fit lines. Given a set of points, draw lines that best fit the points, or more formally with minimum error. When the points are not neatly arranged. Obviously, if we wanted the best accuracy, we could draw a line for each point. This, however, is not a helpful solution.