Week 9

The weighted interval scheduling problem is a lot like the unweighted interval scheduling problem except that each task to be scheduled has a priority or weight to it and we want to schedule jobs such that we have the largest possible weight. With so many variables and components to consider and take into account, a greedy algorithm isn't enough. We need something that is more powerful than greedy algorithms but more efficient than brute-force algorithms.

We use recursion all the time without even thinking about it. Sometimes, however, we do more work than we have to when we come across the same call in different recursive call branches of execution. Instead of recomputing those results, we can use memoization to remember the value of previously calculated results. Every time the recursive function is called, we check the call against a memoization table. If there is no stored result for that call, we run the recursive call and store its result in the memoization table. If there is a stored result, simply return that instead of running the call again.

Instead of memoization, we can also use an algorithm that iterates over subproblems. In this case, we solve the anticipated subproblems and then build up a solution from those. Typically, we have to do some post-processing or code tracing to find the solution steps that led to us attaining the solution's value that we got after the iteration.

Given a plot of points on an xy-plane, find the segments of best fit that minimizes the function. We want a solution that has a minimum amount of error while also having the least number of line segments (otherwise n-1 line segments would always be the optimal solution). We're going to use the tradeoff function E + cL, for some constant c > 0 where E is the sum of sums of the squared errors in each setment and L is the number of line segments, as our metric for an optimal solution. To find the solution, our insight is that if we iterate through the points (starting at the last point¹⁾) and make a multiway decision to include a point in any of a number of line segments.

The knapsack problem is a problem in which we have n items, each of which has a weight (w>0) and a value (v>0). If we have a knapsack with a capacity of W kilograms, how can we fill the knapsack so we can maximize the total value?

We go about solving this problem much like we did with the weighted interval scheduling problem in that we have to make a binary decision to include an item in the solution or not. Unlike weighted interval scheduling, however, items with equal or less weight do not conflict with each other, so we can't stop our algorithm just because we choose an item, we have to keep going to make sure we consider all reasonable combinations. We use a weight limit to designate the amount of weight we can still add to the knapsack after adding previous items. The ongoing weight limit to determine whether or not to include an item.