Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:donohuem:chapter6 [2018/03/27 00:26] – donohuem | courses:cs211:winter2018:journals:donohuem:chapter6 [2018/03/27 01:05] (current) – donohuem | ||
|---|---|---|---|
| Line 18: | Line 18: | ||
| ===== 6.2 Memoization and Iteration ===== | ===== 6.2 Memoization and Iteration ===== | ||
| - | The Weighted Interval Scheduling problem can also be solved using an iterative algorithm as opposed to a recursive one. Both algorithms are dynamic and use memoization. The iterative algorithm also has a runtime of O(n). Both algorithms are dynamic because the divide the main problem into subproblems and then combine computed subproblems to solve the overall problem. The readability of this sections is 8/10. | + | The Weighted Interval Scheduling problem can also be solved using an iterative algorithm as opposed to a recursive one. Both algorithms are dynamic and use memoization. |
| + | |||
| + | | ||
| + | M[0] = 0 | ||
| + | for j-1 to n | ||
| + | M[j] = max(vj + M[p(j)], M[j-1]) | ||
| + | |||
| + | The iterative algorithm also has a runtime of O(n). Both algorithms are dynamic because the divide the main problem into subproblems and then combine computed subproblems to solve the overall problem. The readability of this sections is 8/10. | ||
| + | |||
| ===== 6.3 Segmented Least Squares ===== | ===== 6.3 Segmented Least Squares ===== | ||
| + | The problem arises out of best fit lines. Given a set of points, draw lines that best fit the points, or more formally with minimum error. When the points are not neatly arranged. Obviously, if we wanted the best accuracy, we could draw a line for each point. This, however, is not a helpful solution. | ||
