Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioniii [2012/03/28 02:30] – [The Problem] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioniii [2012/03/28 02:39] (current) – [Algorithm Analysis] mugabej
@@ Line 38: / Line 38: @@
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> for j = 1 to n\\
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[j] = min <sub>1 ≤ i ≤ j</sub> (e[i][j] + c + M[i-1])\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> return M[n]
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> return M[n]\\
+\\
+Just like the Weighted Interval Scheduling Problem, we need to find an algorithm that gives us the solution itself.\\
+** Algorithm to give for the solution itself**
+\\
+>>>>>>>>>>>>>>>>>> FindSegments(j):\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if j = 0:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> output nothing\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> else:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Find an i that minimizes e<sub>i,j</sub> + C + M[i-1]\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Output the segment {p<sub>i</sub>, …, p<sub>j</sub>} and the result of \\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> FindSegments(i-1)
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if
+=====  Algorithm Analysis =====
+\\
+The running time of the algorithm is O(n<sup>2</sup>) since filling in the array M[j] takes us O(n) time for each j.\\
+I give this section 7/10.