Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:thetfordt:chapter6 [2018/03/26 17:56] – created thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter6 [2018/03/26 18:32] (current) – thetfordt
@@ Line 3: / Line 3: @@
 ===== Section 6.1 - Weighted Interval Scheduling: A Recursive Procedure =====
+The section begins by outlining the problem which we are seeking to solve. It is the same interval scheduling problem from earlier in the text, except now, the intervals have weights assigned to them and we want to maximize the total weight.
+The section then outlines a recursive structure for solving this problem. We first consider the final job: either that job is in the optimal solution, or that job is not in the optimal solution. Therefore, if there are j jobs, Opt(j) = max (value(j) + Opt(p(j)),Opt(j-1)), where p(j) is the first available job behind the start time of job j. And this leads directly into the algorithm for computing the optimal solution. If j == 0, we Return 0, otherwise, we return max (value(j) + Opt(p(j)),Opt(j-1)). And note that, within this algorithm we are computing the optimal solution for each j = 1,2,..., n.
+If we just run the algorithm as is, then it would run in polynomial time, having to run through the same recursions over and over. But we have a strategy for combatting this: memoization. We simply keep track of the previously-calculated values, and this way, the runtime is reduced to O(n) if we assume that the input intervals are sorted by their finish times. The section proceeds to walk through a clear example of how to output a solution from the algorithm, that is, the exact jobs scheduled while maintaining linear time.
+I found this section intuitive and straight-forward. I had also grasped the material very well from the class when this was covered. I would rate the readability at 9/10.
+===== Section 6.2 - Principles of Dynamic Programming: Memoization or Iteration over Subproblems =====
+This section opens by speaking about the memoization technique used in 6.1 The section 6.2 will cover this technique in broader terms, as this technique lies at the heart of dynamic programming.
+In the previous section, we used an array to maintain the optimal solution for each value, but we did this using recursion. In this section, we are given an algorithm to do this using an iterative method. It sets the first value in the array M equal to zero. And then for each j = 1,2,..., n, we let M[j] = max(value(j) + M[p(j)],M[j-1]). And this way the calls back into earlier in the array are time-constant as the for-loop progresses. This algorithm runs in O(n) time.
+The section notes that both approaches to calculating this array are very similar, but that we will be using this second iterative approach from now on out. The section then lays out the three basic properties of subproblems (derived from the original problem) that must be true in order to use our dynamic programming techniques.
+(I) There can only be a polynomial number of subproblems.
+(II) The solution to the original problem can be easily computed from the solutions to the subproblems
+(III) There is an intuitive ordering of subproblems from "smallest" to "largest" such that there exists an easy-to-compute recurrence.
+I found this section helpful and brisk. I would rate the readability at 10/10.
+===== Section 6.3 - Segmented Least Squares: Multi-way Choices =====
+In the previous sections, we opened the logic of solving the problems with a binary choice: either the final job lied in the solution or it did not. But this is not always the case. In this section, we will tackle a multi-way choice problem.
+The problem we will be examining has to do with points on an x-y plane. We know how to minimize the sum of squares with a set of points by creating a best-fit line. But if we could have multiple lines? And what if we wanted to minimize both the sums of squares (have an accurate best-fit line), but also minimize the number of lines used in order to minimize the sums of squares.
+Say that we are given a set of points on an x-y plane. We need to create a penalty of partitioning the x-values (to create a new line). We see that the penalty of a partition is
+(i) the number of segments into which we partition P, times a fixed given multiplier C>0
+(ii) For each segment, the error value of the optimal line through that segment.
+Our goal here is to find a partition such that we minimize our penalty. The section walks through a few subproofs before laying out the algorithm itself. First, we call e(i,j) the minimum error of any line with respect to points p_i,...,p_j (points ordered by increasing x-value). The book lays out the fact that if the last segment of the optimal partition is p_i,...,p_n, then the value of the optimal solution is Opt(n) = e(i,n) + C + Opt(i-1). This makes sense to me in an intuitive nature. Additionally, we define Opt(j) on the points p_1,...,p_j to be min ((for 1 <= i <= j) e(i,j) + C + Opt(i-1)). Using these facts, we are able to design an algorithm which directly stems from the logic laid before us.
+The algorithm defines an array M[0,...,n], and sets M[0] = 0. ANd for all pairs with i<=j, we compute the least squares error e(i,j) for the segment p_i,...,p_j. And then for j = 1,2,...,n, we use recurrence of the formula laid out in the previous paragraph to compute M[j]. And then we just return M[n]. In order to determine the runtime of the algorithm as a whole, we note that it takes O(n^2) time to examine all of the pairs. But even further, it takes O(n^3) time to compute all of the e(i,j) values. The second for-loop takes O(n^2) time, yielding a total algorithm runtime of O(n^3).
+I was absent from class during the coverage of this material, so this section was a little more difficult for me to digest. Altough, I found the book's explanations fairly straight-forward. I would rate the readability of this section at 7/10.