Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2012:journals:mike:home [2012/03/01 04:56] – [Section 1: Mergesort] whitem12 | courses:cs211:winter2012:journals:mike:home [2012/03/28 03:18] – [Chapter 6] whitem12 | ||
---|---|---|---|
Line 62: | Line 62: | ||
So if you don't know the constant then you can assume it exists and then check to make sure that it turns out right in the end and then work it back up to find the actual constant involved. | So if you don't know the constant then you can assume it exists and then check to make sure that it turns out right in the end and then work it back up to find the actual constant involved. | ||
+ | ===== Chapter 6 ===== | ||
+ | Dynamic Programing - Break down into sub problems, then build the problems back up to solve the large problem. | ||
+ | ==== Weighted interval scheduling ==== | ||
+ | Recursive algorithm: this is the first step in creating a dynamic algorithm. | ||
+ | === How to do it === | ||
+ | - label the requests, and sort them in order of finishtime | ||
+ | - Think of the optimal solution, either the last item is in it or isn't in it | ||
+ | - Find the optimal solution involving the last one (so ignore all that don't finish before it starts) and the optimal solution that doesn' | ||
+ | |||
+ | This is a problem because the call stack grows at very very fast rate, we want to avoid this, so we introduce the dynamic part. | ||
+ | |||
+ | By memorizing the result of a previous calculation, | ||
+ | |||
+ | You can use the Array of calculation choices to work your way back to find the optimal solution. | ||
+ | |||
+ | ==== Memoization ==== | ||