Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch6 [2018/03/26 21:13] – ahmadh
+++ courses:cs211:winter2018:journals:ahmadh:ch6 [2018/03/27 00:48] (current) – ahmadh
@@ Line 68: / Line 68: @@
 ==== 6.1.4 Comments ====
-TODO later
+This section was pretty interesting. I liked how they introduced a novel concept by straight up diving into an example and explaining things using the example. I had no trouble following the section in class, but even then it was really well-explained in the book. 8/10.
 ===== 6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems =====
@@ Line 88: / Line 88: @@
 ==== 6.2.2 Comments ====
+There wasn't really much to this section. It was pretty much just an iterative version of the recursive solution to the problem in 6.1, followed by a general template for dynamic programming solutions. Not the most interesting section--5/10.
+===== 6.3 Segmented Least Squares: Multi-way Choices =====
+In the previous sections, we developed a recurrence based on a fundamentally binary choice: either the interval n belonged to an optimal solution or it didn’t. In the problem we consider in this section, the recurrence will involve what might be called "multi-way choices": at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution.
+==== 6.3.1 The Problem ====
+Suppose our data consists of a set P of n points in the plane, denoted (x_1, y_1), ..., (x_n, y_n); and suppose x_1 < x_2 < ... < x_n. Given a line L defined by the equation y = ax + b, we say that the error of L with respect to P is the sum of its squared "distances" to the points in P: Error(L, P) = ∑(i=1 -> n)(y_i - a.x_i - b)².
+We will use p_i to denote the point (x_i, y_i). We must first partition P into some number of segments. Each segment is a subset of P that represents a contiguous set of x-coordinates; that is, it is a subset of the form {p_i, p_{i+1}, ..., p{j-1}, p_j} for some indices i ≤ j. Then, for each segment S in our partition of P, we compute the line minimizing the error with respect to the points in S.
+The penalty of a partition is defined to be a sum of the following terms:
+  - The number of segments into which we partition P, multiplied by a fixed constant C > 0.
+  - For each segment, the error value of the optimal line through that segment.
+Our goal in the Segmented Least Squares Problem is to find a partition of minimum penalty.
+==== 6.3.1 Designing the Algorithm ====
+Suppose we let OPT(i) denote the optimum solution for the points p_1, ..., p_i, and we let e_{i,j} denote the minimum error of any line with respect to p_i, p_{i+1}, p_j. (Note: we define OPT(0) = 0.) Then it follows 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).
+And, for the subproblem on the points p_1, ..., p_j, OPT(j) = min{1 ≤ i ≤ j} [e_{i, j} + C + OPT(i - 1))] (6.7).
+We can then come up with the following algorithm:
+	Segmented-Least-Squares(n):
+	   Array M[O... n]
+	   Set M[0]= 0
+	   For all pairs i ≥ j
+	      Compute the least squares error e_{i,j} for the segment p_i, ..., p_j
+	   Endfor
+	   For j = 1, 2, ..., n
+	      Use the recurrence in (6.7) to compute M[j]
+	   Endfor
+	   Return M[n]
+	Find-Segments(j):
+	   If j = 0 then
+	      Output nothing
+	   Else
+	      Find an ithat minimizes e_{i,j} + C + M[i-1]
+	      Output the segment {p_i, ..., p_j} and the result of Find-Segments(i-1)
+	   Endif
+Finally, we consider the running time of Segmented-Least-Squares. First we need to compute the values of all the least-squares errors e_{i,j}. To perform a simple accounting of the running time for this, we note that there are O(n^2) pairs (i, j) for which this computation is needed; and for each pair (i, j), we can use the formula given at the beginning of this section to compute e_{i,j} in O(n^3) time. Thus the total running time to compute all e_{i,j} values is O(n^3).
+For Find-Segments, the algorithm has n iterations, for values j = 1, ..., n. For each value of j, we have to determine the minimum in the recurrence (6.7) to fill in the array entry M[j]; this takes time O(n) for each j, for a total Of O(n^2).
+==== 6.3.2 Comments ====
+One of the more difficult problems to follow, in my opinion. I feel like part of the reason behind that was that it was all theoretical, and hence, difficult to explain. I struggled following it in class initially, as did most other people I believe. I eventually got comfortable with the problem, and the reading cemented that understanding. I feel like I have seen a similar problem before, I just don't remember where. In any case, it was an interesting, albeit difficult, section--7/10.