Week 9

• Readability Score: / 10
• Interest Score: / 10

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.