Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch6 [2018/03/27 00:22] – 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 ====
-TODO later
+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 =====
@@ Line 125: / Line 125: @@
 	   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.