Differences

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

--- courses:cs211:winter2018:journals:nasona:chapter6 [2018/03/25 12:10] – [6.2 Principles of Dynamic Programming] nasona
+++ courses:cs211:winter2018:journals:nasona:chapter6 [2018/03/25 12:15] (current) – [6.1 Weighted Interval Scheduling] nasona
@@ Line 1: / Line 1: @@
 =======6.1 Weighted Interval Scheduling=======
 ==Summary==
+There is no known greedy solution for this problem. Using a straightforward algorithm, we would get an exponential algorithm. To decrease the runtime and redundancy of the computations, we can use memoization. Memoization is the technique of saving values that have already been computed. The runtime of M-Compute-Opt(n), the version of the algorithm that uses memoization, is O(n). However, we are not done. We need to also retroactively compute the components that make up the optimal solution (not just the value). Therefore, we need to define a second part to the algorithm that does that, which takes O(n) time.
 ==Designing a Recursive Algorithm==
@@ Line 27: / Line 28: @@
   * The fact that the algorithm as written take exponential time is due to the redundancy in the number of times it issues each of these calls
   * Solution: store the value of Compute-Opt in a globally accessible place the first time we compute it and then simply use this precomputed value in place of all future recursive calls
-  * Memorization: the technique of saving values that have already been computed
+  * Memoization: the technique of saving values that have already been computed
   * Memorized Compute-Opt would make use of array M[0…n]; M[j] will start with the value “empty” but will hold the value of Compute-Opt(j) as soon as it is first determined