Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioni [2012/03/27 23:37] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioni [2012/03/28 01:13] (current) – [Memoizing the Recursion] mugabej
@@ Line 6: / Line 6: @@
 ===== Designing a Recursive Algorithm =====
 **The Setting**
 >>>>>>>>>>>>>>>> We have n requests labeled 1,...,n\\
 >>>>>>>>>>>>>>>> Each request i has a start time s<sub>i</sub> and a finish time f<sub>i</sub>\\
->>>>>>>>>>>>>>>> Each interval i has a value(weight), v<sub>i</sub>
+>>>>>>>>>>>>>>>> Each interval i has a value(weight), v<sub>i</sub>\\
+>>>>>>>>>>>>>>>> Two intervals are compatible if they don't overlap\\
+>>>>>>>>>>>>>>>> Our Goal is to select a subset S ⊆ {1,...,n} of mutually compatible intervals so as to maximize the sum of the values of the selected intervals, ∑<sub>i ∈ S</sub> v<sub>i</sub>\\
+>>>>>>>>>>>>>>>> If we suppose that the requests are coming in order of non-decreasing finish time: f<sub>1</sub>≤f<sub>2</sub>,...,f<sub>n</sub>,:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> A request i comes before a request j if i<j.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> We define p(j) for an interval j as the largest index i<j such that the intervals i and j are disjoint.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> So i is the leftmost interval that ends before j begins.(We know we are considering jobs in a left to right order where the intervals are increasing from left to right.)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> We define p(j) = 0 if no request i<j is disjoint from j.\\
+>>>>>>>>>>>>>>>> Now let's consider an optimal solution O.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> For the optimal solution O, we can say that: either interval n( the last one) belongs to O or it doesn't.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Let's explore both sides of the situation:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> If n ∈ O, then no interval indexed between strictly between p(n) and n can belong to O because intervals p(n)+1, p(n) + 2,...,n-1 all overlap with n by definition.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> In addition, if n ∈ O, then O must include an optimal solution to the problem consisting of requests {1,2,...,p(n)}: otherwise, we could replace O's choice of requests from {1,...,p(n)} with a better one, with no danger of overlapping request n.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> If n ∉ O, then O is equal to the optimal solution to the problem consisting of requests {1,...,n-1}: we are assuming that O doesn't include n, thus if it doesn't choose the optimal set of requests from {1,...,n-1}, then we could replace if with a better one.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> So in brief, finding the optimal solution on intervals :1,2,...,n} involves looking at the optimal solutions of smaller problems of the form {1,2,...,j}.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> For any value of j in {1,2,...,n},let O<sub>j</sub> denote the optimal solution to the problem consisting of requests {1,2,...,j}, and let OPT(j) denote the value of this solution.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT(0) =0, which is conventionally the optimum solution over an empty set of intervals.\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Our goal is to find O<sub>n</sub> with value OPT(n).\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> So, from what we have argued above, for the case j=n, either j ∈ O<sub>j</sub> in which case OPT(j) = v<sub>j</sub> + OPT(p(j)), or j∉ O<sub>j</sub> in which case OPT(j) = OPT(j-1).\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Thus from this, we can say that:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT(j) = max(v<sub>j</sub> + OPT(p(j)),OPT(j-))\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Request j belongs to the optimal solution on the set {1,2,...,j} if    and      only if:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>  v<sub>j</sub> + OPT(p(j)) ≥ OPT(j-1).\\
+\\
+A recursive algorithm follows from this extensive discussion:\\
+\\
+**Algorithm**
+\\
+>>>>>>>>>>>>>>>> Compute-OPT(j)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if j = 0:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return 0
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> else:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return max(v<sub>j</sub> + Compute-OPT(p(j)), Compute-OPT(j-1))\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 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.