Differences

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

--- courses:cs211:winter2018:journals:bairdc:chapter6 [2018/03/27 02:35] – [6.1 – Weighted Interval Scheduling: A Recursive Procedure] bairdc
+++ courses:cs211:winter2018:journals:bairdc:chapter6 [2018/03/27 03:46] (current) – [6.1 – Weighted Interval Scheduling: A Recursive Procedure] bairdc
@@ Line 24: / Line 24: @@
 M-Compute-Opt(n)
 </code>
+Overall, I'd give this section a 7/10 on readability and interestingness.
 ===== 6.2 – Principles of Dynamic Programming: Memoization or Iteration over Subproblems =====
+Basic Outline of Dynamic Programming:
+  - There's a polynomial number of subproblems.
+  - The original problem's solution can easily be computed from the subproblems' solutions.
+  - There's an ordering of the subproblems from smallest to largest with a simply computable recurrence.
+There is a sort-of chicken and egg relationship between subproblems and recurrences in dynamic programming. It isn't clear that a collection of subproblems will be useful until you find the linking recurrence. However, it can also be difficult thinking about recurrences without their subproblems.
+Overall I'd give this section a 10/10 on readability and a 8/10 on interestingness.
 ===== 6.3 – Segmented Least Squares: Multi-way Choices =====
+This problem arises from the need to fit a line to some data points to achieve a "best fit." What needs to be optimized is the fewest number of best fit lines possible to achieve the best fit. There are a lot of repeated checks of each point's error in a naive, brute-force solution. These checks can be memoized. The following implementation in the below two methods incorporate memoization to achieve a dynamic programming solution.
+<code>
+INPUT: n, p1,…,pn , c
+Segmented-Least-Squares()
+    M[0] = 0
+    e[0][0] = 0
+    for j = 1 to n
+        for i = 1 to j
+            e[i][j] = least square error for the segment pi,…, pj
+    for j = 1 to n
+        M[j] = min 1 ≤ i ≤ j (e[i][j] + c + M[i-1])
+    return M[n]
+FindSegments(j):
+    if j = 0:
+        output nothing
+    else:
+        Find an i that minimizes ei,j + c + M[i-1]
+        Output the segment {pi,...pj}
+        FindSegments(i-1)
+</code>
+Overall, I'd give this section a 9/10 on readability and interestingness.