| Having solved the Weighted Interval Scheduling problem using a recursive approach, we will now look at it through a different perspective using an iterative approach. The recursive approach returns an optimal solution to the Weighted Interval Scheduling problem in polynomial-time. In our iterative approach, we will again use an array M to keep track of the values, and when computing a value we can look at the values that come earlier in the array. Once we have the full array M, we have the solution to the problem, and can run FIND-SOLUTION to return the actual optimal solution itself. We can directly compute the entries in M through an iterative for loop, instead of using memoized recursion. We start with M[0] = 0, and increment j, looking to determine the optimal value of M[j]. The running time of this algorithm is O(n), since we are just running through a single for loop from 1 to n. Thus, we now have two different ways to solve the Weight Interval Scheduling Problem: a recursive approach, and an iterative approach. These approaches help us to form a pattern for developing an algorithm based on dynamic programming: find a collection of subproblems derived from the original problem that satisfies a few basic properties. These guidelines are: 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 subproblems, 3) there is a natural ordering on subproblems from smallest to largest, 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. It can be useful sometimes to first defeine a recurrence using reasoning about the structure of the optimal solution, or by the other way around. It depends on the problem. This section was easy to read after having discussed it well in class. I would give it a 9/10. | Having solved the Weighted Interval Scheduling problem using a recursive approach, we will now look at it through a different perspective using an iterative approach. The recursive approach returns an optimal solution to the Weighted Interval Scheduling problem in polynomial-time. In our iterative approach, we will again use an array M to keep track of the values, and when computing a value we can look at the values that come earlier in the array. Once we have the full array M, we have the solution to the problem, and can run FIND-SOLUTION to return the actual optimal solution itself. We can directly compute the entries in M through an iterative for loop, instead of using memoized recursion. We start with M[0] = 0, and increment j, looking to determine the optimal value of M[j]. The running time of this algorithm is O(n), since we are just running through a single for loop from 1 to n. Thus, we now have two different ways to solve the Weight Interval Scheduling Problem: a recursive approach, and an iterative approach. These approaches help us to form a pattern for developing an algorithm based on dynamic programming: find a collection of subproblems derived from the original problem that satisfies a few basic properties. These guidelines are: 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 subproblems, 3) there is a natural ordering on subproblems from smallest to largest, 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. It can be useful sometimes to first defeine a recurrence using reasoning about the structure of the optimal solution, or by the other way around. It depends on the problem. This section was easy to read after having discussed it well in class. I would give it a 9/10. |
| In the previous section, we looked at a recurrence based on a fundamentally binary choice: either include an option or don't include it. The problem in this instance maintains 'multi-way' choices: at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution. The basic of this problem lies to trying to find the line-of-best-fit for a set of statistical data points, trying to minimize the 'error' of the fit, which is calculated by finding the sum of the squared distances between the line and the points. We can easily derive a closed-form solution for calculating this using calculus. Usually, we only use a single line when calculating error of points. However, what if we wanted to use two lines to minimize the error more. We could continue to add lines to minimize the error until we had n total lines and an error of 0. However, this solution is too trivial. We could also try to find a solution using ONLY two lines, however, this requires us to be able to look at the data we are given, instead of dynamically responding to data provided. We want to be able to dynamically adapt to find the best number of lines to fit the data to minimize the error. This problem is called the Segmented Least Squares Problem. This is a fundamental instance of an issue in statistics known as //change detection//: Given a sequence of data points, we want to identify a few points in the sequence at which a discrete change occurs, or in this case, a change in linear approximations. To formulate the problem, we are given a set of points. We need to first partition P into a number of segments, where each segment is a subset of P that represents a contiguous set of x-coordinates. Then, for each segment S, we compute the line to minimize the error. The penalty for a partition is defined as the sum of the following terms: 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. The goal is to find a partition with the minimal penalty. The penalty multiplier C determines our ability to use additional lines to a greater or a lesser extent. In designing the algorithm, we want a polynomial number of subproblems, which we can build up using a recurrence. The last point pn belongs to a single segment in the optimal partition, which begins at some earlier point. If we know the identity of the last segment, we can remove all those points from consideration, and look at the smaller problem. '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). | In the previous section, we looked at a recurrence based on a fundamentally binary choice: either include an option or don't include it. The problem in this instance maintains 'multi-way' choices: at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution. The basic of this problem lies to trying to find the line-of-best-fit for a set of statistical data points, trying to minimize the 'error' of the fit, which is calculated by finding the sum of the squared distances between the line and the points. We can easily derive a closed-form solution for calculating this using calculus. Usually, we only use a single line when calculating error of points. However, what if we wanted to use two lines to minimize the error more. We could continue to add lines to minimize the error until we had n total lines and an error of 0. However, this solution is too trivial. We could also try to find a solution using ONLY two lines, however, this requires us to be able to look at the data we are given, instead of dynamically responding to data provided. We want to be able to dynamically adapt to find the best number of lines to fit the data to minimize the error. This problem is called the Segmented Least Squares Problem. This is a fundamental instance of an issue in statistics known as //change detection//: Given a sequence of data points, we want to identify a few points in the sequence at which a discrete change occurs, or in this case, a change in linear approximations. To formulate the problem, we are given a set of points. We need to first partition P into a number of segments, where each segment is a subset of P that represents a contiguous set of x-coordinates. Then, for each segment S, we compute the line to minimize the error. The penalty for a partition is defined as the sum of the following terms: 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. The goal is to find a partition with the minimal penalty. The penalty multiplier C determines our ability to use additional lines to a greater or a lesser extent. In designing the algorithm, we want a polynomial number of subproblems, which we can build up using a recurrence. The last point pn belongs to a single segment in the optimal partition, which begins at some earlier point. If we know the identity of the last segment, we can remove all those points from consideration, and look at the smaller problem. '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 the following occurrence: **For the subproblem on the points pi,...,pj, OPT(j) = min[1<=i<=j](ei,j + C + OPT(i-1), and the segment pi,..,pj is used in an optimum solution for the suproblem IF AND ONLY IF the minimum is obtained using index i.** Like the Weighted Interval Scheduling Problem, the correctness of the algorithm can be proved using induction. Additionally, we can trace back through the array M to compute an optimum partition. The running-time of computing the values for ei,j for all (i,j) pairs is O(n^3), since there are n^2 pairs, and to compute the error takes O(n). Once all the error values have been calculated, it takes O(n) to find the value for each value of j, so a total run time of O(n^2) once all the ei,j pairs have been determined. This section was harder to follow, but the pictures made it easier to understand. Understanding the run-time of the algorithm wasn't well explained in class or in the book. I would give this section a 5/10 overall. |
