Differences

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

--- courses:cs211:winter2014:journals:alyssa:chapter_6.3 [2014/03/25 21:27] – hardnetta
+++ courses:cs211:winter2014:journals:alyssa:chapter_6.3 [2014/03/25 23:51] (current) – hardnetta
@@ Line 16: / Line 16: @@
   * For all pairs i < = j:
   * compute the error e_i,j for the segment p_i,...,p_j
+(end for)
+  * For j=1,2,...,n:
+  * compute M[j]=min(e_i,j+C+OPT(i-1)) for 1 < = i < = j
+  * return M[n]
+Find-Segments(j):
+  * if j=0 then return nothing
+  * else:
+  * find an i that minimizes e_i,j+C+M[i-1]
+  * return the segment {p_i,...,p_j} and the result of Find-Segments(i-1)
+Computing all e_i,j values is O(n^3) running time, and the remaining problem runs in O(n^2) time.
+I would rate this section a 7. I understood it, but I feel like they could have done a better job setting up the problem. I think the motivation for the problem was explained better in class than in this section.