Differences

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

--- courses:cs211:winter2012:journals:mike:home [2012/03/28 03:26] – [Memoization] whitem12
+++ courses:cs211:winter2012:journals:mike:home [2012/03/28 04:00] (current) – [Adding a variable] whitem12
@@ Line 93: / Line 93: @@
 If working backwards gets you the solution its probably going to be the way to go.
+==== Least Squares ====
+Finding the best fit line.  Want to minimize the square of the deviations of data from a line.  Data is given, find the line.  There isn't always one line, sometimes multiple lines, but we want creating a new line to have a penalty, otherwise there would be a line from each data point to another datapoint and the SSE (sum of squares error) = 0.
+This can be made into a dynamic function by working backwards, you find the SSE for the last three points (otherwise it's 0 so it's easy) and then compair whether making a new partition is going to be more effective in minimizing the SSE + penalty or if it's more useful to just adjust the original line.
+This total adds up to O(n^2)
+==== Adding a variable ====
+The subset sums problem is where each event has a value and a weight.  There is a limit on the weight you can take on, so you want to optimize the sum of the values given a maximum weight W.  There is no greedy algorithm to find this solution, so we look for dynamic programming.  We build a 2D table (matrix) of optimal solutions to find the overall optimal solution for all w's less than W.  This way it can be computed quickly, though large amounts of memory may be required.
+The knapsack problem is one where each element has a value and a weight.  You want to maximize the sum of the values while keeping the weight below a certain amount.  This is solved the same was as the scheduling problem.