Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch6 [2018/03/26 20:50] – ahmadh
+++ courses:cs211:winter2018:journals:ahmadh:ch6 [2018/03/27 00:48] (current) – ahmadh
@@ Line 15: / Line 15: @@
 Thus, for any value of j between 1 and n, let O_j denote the optimal solution to the problem consisting of the requests {1, ..., j}, and let OPT(j) denote the value of the solution. Based on our reasoning earlier, we can say that:
-	OPT(j) = max(v_j + OPT(p(j)), OPT(j - 1))
+	(6.1) OPT(j) = max(v_j + OPT(p(j)), OPT(j - 1))
 As such, a request j belongs to an optimal solution to the set {1, 2, ..., j} if and only if v_j + OPT(p(j)) ≥ OPT(j - 1).
@@ Line 32: / Line 32: @@
 ==== 6.1.2 Memoizing the Recursion ====
+A fundamental observation, which forms the second crucial component of a dynamic programming solution, is that our recursive algorithm Compute-Opt is really only solving n+1 different subproblems: Compute-0pt(0), Compute-Opt(1), ..., Compute-0pt(n). The fact that it runs in exponential time is simply due to the redundancy in the number of times it issues each of these calls. We could store the value of Compute-0pt in a globally accessible place the first time we compute it and then simply use this precomputed value in place of all future recursive calls in order to drastically improve the runtime. This is called memoization.
+The memoized version of our algorithm is as follows:
+	M-Compute-Opt(j):
+	   If j = 0
+	      then Return 0
+	   Else if M[j] is not empty
+	      then Return M[j]
+	   Else
+	      Define M[j] = max(v_j + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
+	      Return M[j]
+	   Endif
+Since we only ever need to compute the value of M[j] for a particular value of j once, we do at most n such computations. Every other step in the algorithm is O(1). Therefore, the M-Compute-Opt algorithm runs in O(n) time (assuming that the input intervals are sorted by their finish times).
+==== 6.1.3 Computing the Solution in Addition to Its Value ====
+So far, we have simply computed the value of an optimal solution. It would be easy to extend M-Compute-0pt so as to keep track of an optimal solution in addition to its value: we can trace back through the array M to find the set of intervals in an optimal solution. The following algorithm does exactly that:
+	Find-Solution(j):
+	   If j = 0 then
+	      Output nothing
+	   Else
+	      If v_i+ M[p(j)] ≥ M[j-1] then
+	         Output j together with the result of Find-Solution(p(j))
+	      Else
+	         Output the result of Find-Solution(j-1)
+	      Endif
+	   Endif
+Since Find-Solution calls itself recursively only on strictly smaller values, it makes a total of O(n) recursive calls; and since it spends constant time per call, the overall running time of the algorithm is O(n).
+==== 6.1.4 Comments ====
+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 =====
+In the previous section, we developed a polynomial-time solution to the Weighted Interval Scheduling Problem by first designing an exponential-time recursive algorithm and then converting it (by memoization) to an efficient recursive algorithm. We now formulate an essentially equivalent version of the algorithm that most explicitly captures the essence of the dynamic programming technique, and will serve as a general template for the algorithms we develop in later sections.
+==== 6.2.1 The Iterative Algorithm ====
+We can directly compute the entries in the array M by an iterative algorithm, rather than using memoized recursion. We just start with M[0] = 0 and keep incrementing j; each time we need to determine a value M[j], the answer is provided by (6.1). The algorithm is as follows:
+	Iterative-Compute-Opt:
+	   M[0] = 0
+	   For j = l, 2, ..., n
+	      M[j] = max(v_i + M[p(j)], M[j-1])
+	   Endfor
+The running time of Iterative-Compute-0pt is O(n), since it runs for n iterations and spends constant time in each iteration.
+==== 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.