Chapter 6

The problem with greedy algorithm is that no natural greedy algorithm that works. The problem with divide and conquer algorithm is that it reduces the program to a faster running time, but not necessarily able to reduce exponential algorithms to polynomial runtime. So, we look at Dynamic programming, which is very close to brute force.

We now have jobs of various weights that we need to solve. This is not easily done by greedy algorithms.

Let's suppose these intervals are sorted in order in terms of their finish time. Request i comes after request j if i < j for f1 ⇐ f2 ⇐ ⇐ f3 ⇐ … ⇐ fn. Let's assume that i is the leftmost interval that finishes before j begins. p(j) = 0 if no request i < j is disjoint from j.

The basic way to think of this problem is either interval n is in the optimal solution, or it is not. If it is, then we won't be able to take in any intervals that is overlapping n. If it is not, then we consider the previous interval before n.

OPT(j) = max(vj + OPT(p(j)), OPT(j - 1))

n belongs to the optimal solution, O, if the first of the options above is at least as good as the second, or mathematically, interval j belongs to O if vj + OPT(p(j)) >= OPT(j - 1)

Algorithm on page 254.

“Compute-Opt(j) correctly computes OPT(j) for each j = 1, 2, …, n.” (Proof on page 255)

By storing the value of Compute-Opt in a globally accessible storage as soon as we compute it for the first time, we can reduce the exponential runtime by just referring to this storage for future recursions.

Algorithm on page 256.

“The running time of M-Compute-Opt(n) is O(n) (assuming the input intervals are sorted by their finish times).” (Proof on page 257)

We can now just refer back to the memoization to get not only a value for the optimal solution, but also the optimal solution itself.

Algorithm on page 258.

The runtime would now be O(n).

The key is memoization in the array M. We store the value computed to M and then we can just refer back to it, without having to calculate it again and again.

Algorithm on page 259.

The algorithm runs in O(n) time as it runs for exactly n iterations, with constant time in each of them.

To develop an algorithm through dynamic programming, we need different subproblems derived from the original problem that satisfy the following:

1. There are only a polynomial number of subproblems.
2. The solution to the original problem can be easily computed from the solutions to the subproblem.
3. There is a natural ordering on subproblems from smallest to largest.

The previous problem included a binary choice: either to include n, or not. Here, we have multi-way choices: at each step, we have a polynomial number of possibilities to consider for an optimal solution.

We are dealing with “line of best fit”. The line tries to minimize error of the data. If the data points are almost straight, calculus can easily solve it. But if the data is curved, or bent, or anything else that is NOT straight, we have a problem. For example, take a look at figure 6.7. Any single line of best fit would have a huge error.

So, instead of choosing a single line of best fit, we design an algorithm to draw multiple lines to minimize error. But, this would mean we could actually draw n-1 lines to fit all the data points in the line exactly, this reducing the error to 0.

We could also code in such a way that we draw 2 lines at most. But this wouldn't work for something like the one in figure 6.8.

Thus, we need an algorithm to draw least number of lines to minimize error.

We are given a set of points P = {(x1, y1), (x2, y2), … (xn, yn)}, with x1 < x2 < … < xn. We first divide P into segments and draw the line that minimizes error. A penalty of a partition is a sum of:

1. The number of segments into which we partition P, times a fixed, given multiplier C > 0.
2. For each segment, the error value of the optimal line through that segment.

Our goal is to find a partition of minimal penalty.

We observe that the last point pn belongs to a single segment in the optimal partition that begins at some earlier point pi. If we knew the last segment, we can then consider only points p1 through pn-1.

Lets say OPT(i) denotes the optimum solution for the points p1 through pi and we let ei,j denote the minimum error of any line with respect to pi, pi+1, …, Pj. Thus, “If the last segment of the optimal partition is pi, …, pn, then the value of the optimal solution is OPT(n) = ei,n + C + OPT(i-1).”

Thus, we have defined the recurrence: OPT(j) = min(ei,j + C + OPT(i - 1))

Algorithm on page 265.

Backtracking algorithm using memoization on page 266.

With O(n²) pairs of (i,j) plus the calculation of ei,j in O(n) time would leave this algorithm at O(n³) time. After this, the algorithm has n iterations and for each value of j, we need to find the minimum in the recurrence and fill it in M. This takes an addition O(n) time, thus leaving the algorithm at O(n²) time after all ei,j have been determined.

Let's suppose we have n items, each of various value and takes up different number of spaces in a knapsack. Now, we need to fill in our knapsack to make it most valuable, given that we have limited space.

Like the weighted interval schedule, the basic idea for this algorithm is whether or not an item i is present in the knapsack. However, unlike the weighted interval schedule, we not only consider the ith item with i-1th item, but with all other items, to maximize the value. So we have:

1. If n doesn't belong to O, then OPT(n, W) = OPT(n - 1, W), since we can simply ignore item n.
2. If n belongs to O, then OPT(n, W) = wn + OPT(n - 1, W - wn), since we now seek to use the remaining capacity of W - wn in an optimal way across items 1, 2, …, n - 1.

If the nth item is too big, we must have OPT(n, W) = OPT(n - 1, W)

Thus, mathematically, we have:

If w < wi then OPT(i, w) = OPT(i - 1, w). Otherwise, OPT(i, w) = max(OPT(i - 1, w), wi + OPT(i - 1, w - wi)).

Algorithm on page 269.

Figure 6.11 shows a 2D array to visualize this.

The runtime of this algorithm is proportional to the number of entries in the table because we can compute the values in M in O(1) time as they are already stored in an array. The Subset-Sum(n, W) Algorithm computes the optimal value of the problem in O(nW) time. Now, given the table M of the optimal values of the subproblems, the optimal set S can be found in O(n) time.

Figure 6.12 shows how this is worked out.

No questions. Class helps, a lot lot!

And the chapter wasn't that hard to understand either, probably because we discussed it in class before I actually went through the chapter.

It was easily readable, and understandable.

And it was interesting to know how, after learning those tough Divide-and-Conquer algorithms and Greedy Algorithms, they still have a drawback and Dynamic Programming helps it.

And we did a dynamic programming in our finance class today. Very interesting!