Differences

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

--- courses:cs211:winter2014:journals:onye:home [2014/02/27 00:19] – [Section 3.6] ekentao
+++ courses:cs211:winter2014:journals:onye:home [2014/03/27 03:53] (current) – [Section 5.5] ekentao
@@ Line 90: / Line 90: @@
 To see that these algorithms work, obsrve that  if S is any nonempty proper subset of the set of vertices, the minimum cost edge extending from that set to a vertex not in that set must be included in the minimum spanning tree. If you have a spanning tree where it isn't used, it can replace any edge extending from S to a vertex out of S for a minimaler spanning tree.
+===== Section 5.3 =====
+Another example of a divide and conquer algorithm is used to count the numer of inversions in a scrambled list. This can be used to measure the similarity between two people's rankings of a particular subject. It works by simply using mergesort and counting the number of inversions observed along the way. It runs in O(n log n) time, just like merge sort.
+==== Section 5.4 ====
+Finding the Closest pair of point surprsingly has a O(n log n) solution, so it's an improvement on the O(n^2) brute force algorithm. This solution works taking the set of points P and sorting them in terms of their x coordinate and then sorting them again in terms of their y coordinates creating lists Px and Py. Then, using Px creating the lists Q and R where Q consits of the half points with the lower x coordinates and R contains the rest. Use Px and Py to construct Qx, Qy, Rx, and Ry of points of Q and R sorted in terms of x and sorted in terms of y. Recursively call the function using Qx and Qy to find the closest pair of points in Q, and using Rx and Ry to to find the closet set points in Q and in R. Then let delta be the smaller of the two distances. Let x be the x coordinate of the rightmost point of Q and let L be the line with constant x-value of x. Let S be the set of points whose distance from L is less than delta and Sy that set sorted in terms of y values (constructed using Py). Now, it turns out that any two points whose distance is less than delta must lie within 15 of one another in the sorted list Sy. To see this, consider a grid with boxes of length and with delta/2 around the line L extending two boxes from either side of L (to get a distance of delta from L). Each box can contain only one point since they belong to only one side and delta is a minimum in that case. So if a point is separated by 15 people it'll go through at least 3 rows so the total distance will be at least 3 delta / 2  which is greater than delta. So comparing each point with points up to 15 units ahead of itself will find the minimum in O(n) time. With the sorting, the entire algorithm runs in O(n log n) time.
+==== Section 5.5 ====
+Multiplying integers. Separate the values into a large end and small end like n = x1*2^(n/2) + x0. Expand the multiplication and rmeember to use (x1 + x0)(y1 + y0) = x1*y1 + x0*y1 + x1*y0 + x0*y0 so you can calculate three multiplications (x1*y1, x0*y0, and (x1+x0)(y1+y0)) instead of 4 (x1*y1,x0*y0,x1*y0,x0*y1), which would result in a quadratic algorithm just like the brute force solution (which can be seen for the general form of creating a recursive procedure whose running time satisfies the recurrence relation T(n) = q*T(n/2) + cn when q > 2)
+==== Section 6.1 ====
+Dynamic program is similar to divide and conquer because we solve a larger problem by solving smaller problems and combining the solutions. It differs due to the fact that the computations done on certain subproblems "overlap", or can inform the computations of other solutions. Because this, the process of memoization, where computed results are stored in an array, can be used to create efficient algorithms.
+==== Section 6.2 ====
+The process of memoization only computes the value of the solution. In order to obtain the actual solution one must look at the method used to combine the solutions. In the case of the interval scheduling problem, the value of the vj + M[p(j)] is compared to the value of M[j-1] and that value is stored in M[j]. Thus, you can determine the solution by computing these values and seeing which is stored in M[j]. If it is the first, the solution includes j, if it is the second, then it does not include vj.
+Once the p function is computed the algorithm runs in O(n) time, but computing the p function takes n log n so the total running time is O(n log n) time.
+==== Section 6.3 ====
+Segmented least squares is a problem that can be solved efficiently using dynamic programming practices. The problem is an extension of the problem of finding the line of best fit through a set of lines. In this problem, one can use several lines, but the there is a cost function that cL + E, where L is the number of lines used and E is the total square error of all the lines.
+A direct implementation of the dynamic programming scheme results in an O(n^3) running time but it is possible to make the computation of all the square erros more efficient to bring the total cost down to O(n^2)
+==== Section 6.4 ====
+This version of the knapsack problem is as follows: You are given a list of N items each with "weights" and "values". You have a specified weight limit, and must find a set that maximizes total value while coming under the weight limit. This case differs because the number of variables is two instead of 1, resulting in a 2-D array. Still, dynamic programming applies and the algorithm that results runs in O(NW) time