Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:garrett:entries:week_9 [2012/03/28 03:39] – 6.3 garrettheath4 | courses:cs211:winter2012:journals:garrett:entries:week_9 [2012/03/28 04:04] (current) – made ratings a table garrettheath4 |
|---|
| |
| ===== Chapter Scores ===== | ===== Chapter Scores ===== |
| * **Readability Score**: FIXME / 10 {{:courses:cs211:winter2012:journals:garrett:entries:rating_2.png?100|}} | | **Readability Score** | 6 / 10 | {{:courses:cs211:winter2012:journals:garrett:entries:rating_3.png?nolink&100|}} | |
| * **Interest Score**: FIXME / 10 {{:courses:cs211:winter2012:journals:garrett:entries:rating_3_5.png?100|}} | | **Interest Score** | 8 / 10 | {{:courses:cs211:winter2012:journals:garrett:entries:rating_4.png?nolink&100|}} | |
| |
| ===== Readings ===== | ===== Readings ===== |
| === 6.3: Segmented Least Squares === | === 6.3: Segmented Least Squares === |
| Given a plot of points on an xy-plane, find the segments of best fit that minimizes the function. We want a solution that has a minimum amount of error while also having the least number of line segments (otherwise ''n-1'' line segments would always be the optimal solution). We're going to use the **tradeoff function** ''E + cL'', for some constant ''c > 0'' where ''E'' is the sum of sums of the squared errors in each setment and ''L'' is the number of line segments, as our metric for an optimal solution. | Given a plot of points on an xy-plane, find the segments of best fit that minimizes the function. We want a solution that has a minimum amount of error while also having the least number of line segments (otherwise ''n-1'' line segments would always be the optimal solution). We're going to use the **tradeoff function** ''E + cL'', for some constant ''c > 0'' where ''E'' is the sum of sums of the squared errors in each setment and ''L'' is the number of line segments, as our metric for an optimal solution. |
| | To find the solution, our insight is that if we iterate through the points (starting at the last point((The "last" point means the point with the largest ''x'' value.))) and make a **multiway** decision to include a point in any of a number of line segments. |
| |
| |
| === 6.4: Subset Sums and Knapsacks === | === 6.4: Subset Sums and Knapsacks === |
| | The **knapsack problem** is a problem in which we have ''n'' items, each of which has a weight (''w>0'') and a value (''v>0''). If we have a knapsack with a capacity of ''W'' kilograms, how can we fill the knapsack so we can maximize the total value? |
| |
| | We go about solving this problem much like we did with the weighted interval scheduling problem in that we have to make a **binary** decision to include an item in the solution or not. Unlike weighted interval scheduling, however, items with equal or less weight do not conflict with each other, so we can't stop our algorithm just because we choose an item, we have to keep going to make sure we consider all reasonable combinations. We use a **weight limit** to designate the amount of weight we can still add to the knapsack after adding previous items. The ongoing weight limit to determine whether or not to include an item. |
| |
| |
