Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioni [2012/03/28 00:33] – [Designing a Recursive Algorithm] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioni [2012/03/28 01:13] (current) – [Memoizing the Recursion] mugabej
@@ Line 46: / Line 46: @@
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if\\
 \\
+Algorithm correctness directly follows by induction on j: Compute-OPT(j) correctly computes OPT(j) for each j =1,2...,n\\
+\\
+But the problem with our algorithm is that our algorithm can take exponential time for reasonably sized problems. The Fibonacci problem is an illustrious instance of this case. We now provide the solution.\\
+===== Memoizing  the Recursion=====
+\\
+By the Memoization technique, we can simply store the  value of each Compute-OPT in a globally accessible structure the first time we compute it and simply use this precomputed value in place for all future recursive calls.\\
+**Algorithm with Memoization**
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M-Compute-OPT(j)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if j =0:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  Return 0\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> elif M[j] is not empty:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return M[j]\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Else:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[j] = max(v<sub>j</sub> + M-Compute-OPT(p(j)), M-Compute-OPT(j-1))
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return M[j]\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if\\
+** Analysis of the Memoized algorithm **
+\\
+  * The running time of M-Compute-OPT(n) is O(n) assuming input intervals are sorted by their finish time\\
+\\
+** Computing a Solution in Addition to its Value**
+\\
+  * M-Compute-OPT algorithms gives us the value of an optimal solution. But we also need to know the optimal solution(made of a set of non overlapping intervals) itself.
+  * Following is the algorithm to efficiently find the solution:\\
+\\
+>>>>>>>>>>>>>>>> M-Compute-Opt(n)\\
+>>>>>>>>>>>>>>>> Find-Solution(n)\\
+>>>>>>>>>>>>>>>> def Find-Solution(j):\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if j = 0:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> output nothing\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> elif vj + M[p(j)] > M[j-1]:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> print j\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Find-Solution(p(j))\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> else:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Find-Solution(j-1)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if\\
+\\
+Given an array M of the optimal values of the sub-problems, Find-solution returns an optimal solution in O(n) time.\\
+\\
+\\
+This section was really interesting, and I enjoyed reading and writing about it, and I give it a 9/10.