Differences

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

--- courses:cs211:winter2014:journals:sam:home [2014/03/10 02:39] – odells
+++ courses:cs211:winter2014:journals:sam:home [2014/04/02 02:18] (current) – [Readability] odells
@@ Line 242: / Line 242: @@
 What is the simplest algorithm to count inversions? We could look at every pair of numbers (ai, aj) and determine whether they constitute an inversion; this would take O(n^2) time. We can achieve O(n log n) time, though!
-But how? We set m
+But how? We set m = [n/2] and divide the list into two pieces, a1-->am and am+1 --> an. We first count the number of inversions in each of these two halves. The trick is that we must do that in O(n) time. To help with counting the number of inversions, between the two halves, we will make the algorithm recursively sort the numbers in the two halves as well. Having the recursive step do a bit more work (sorting as well as counting) will make the "combining" portion of the algorithm easier. So, the crucial routine in this process is Merge-and-Count.
+Our merge-and-count routine will walk through the sorted lists A and B, removing elements from the front and appending them to the sorted list C. In a given step, we have a current pointer into each list. We will then compare the elements ai and bj, remove the smaller one from its list, and append it to the end of list C. As A and B are sorted, we will count the number of inversions fairly easily. If we append an item from list a, then there are no inversions, but if the smallest item is in list B, then we know that it is inverted with everything in list A because it comes after all of them. We then increase our inversions count by the number of items currently in list A, then continue with our comparisons.
+** Thm. 5.7: ** The sort-and-count algorithm correctly sorts the input list and counts the number of inversions; it runs in O(n log n) time for a list with n elements.
 ====5.4====
+Finding the right way to merge the solutions for this problem can be tricky. The problem: finding the closest pair of points. Given n points, in the plane, find the pair that is closest together. M. I. Shamos and D. Hoey considered this problem in the early 1970s.
+We begin with some notation: P = {p1-->pn} where pi has co-ords (xi,yi). d(pi,pj) denotes the standard Euclidean distance between the points pi and pj. Our goal is to find a pair of points that minimizes d(pi,pj).
+We will find the closest pair of points in one half and the closest pair of points in the other half and then use this information to get the overall solution in linear time.
+The first half, Q, and the second half, R, will be considered one at a time. We will find the closest pair of points in Q and R by generating four lists, Qx, which has the points in Q sorted by increasing x co-ords, and Qy, which has the points in Q sorted by decreasing x co-ords, and analagous lists Rx and Ry. We now recursively determine a closest pair of points in both Q and R with access to these lists we have generated.
+Now, we may have already found the closest points in our total set, but we must check to make sure. We will call D the minimum of d(q0,q1) and d(r0,r1). Now, we will imagine that there is a line dividing Q from R, and look for points within distance D of the line L, because only points within our current minimum D have a chance of being closer together than our current set of smallest distance points.
+This algorithm runs in O(n log n) time.
 ====5.5====
+We now turn to consider integer multiplication. The algorithm we were taught to do this in elementary school is quite efficient: you compute many partial products before adding them all together to get the final product. However, this algorithm runs in O(n^2), which we can improve upon by using a different, recursive way of performing the multiplication.
+We will use only three recursive calls so that we get q=3 and our less-than-n^2 running time; the attempted version of the algorithm that is q=4 is n^2 and thus not an improvement!
+The running time of Recursive-Multiply on two n-bit factors is O(n^1.59).
+====Readability====
+Liked this section! I had to wait to do the part about integer multiplication until we'd talked about it in class, but the other sections were very understandable. 9/10.
+=====Summary of 6.1-6.4=====
+====6.1====
+Sometimes, there won't be a greedy solution to any given problem. Dynamic Programming can oftentimes look quite similar to brute-force search. It systematically works through the exponentially large set of possible solutions, BUT it does this without ever examining them all explicitly. We will build a dynamic-programming solution to the weighted interval scheduling problem.
+Our first solution is, unfortunately, exponential:
+Compute-Opt(j):
+    if j=0
+        Return 0
+    else:
+        Return max(Vj + Compute-Opt(p(j)), Compute-Opt(j-1)
+    endif
+It is exponential only because we are re-computing values multiple times; if we were to memoize the values (store them in an array as we compute them) then we can bring the running time down to O(n).
+====6.2====
+Now we want to turn our recursive solution into an iterative one. It is important to note that we can directly compute the entries in M by an iterative algorithm, rather than using memoized recursion. We simply start with M[0]=0 and keep incrementing j; each time we need to determine a value M[j], it is provided by our previous algorithm. It looks like this:
+Iterative-Compute-Opt:
+    M[0]=0
+    For j = 1...n
+        M[j] = max(Vj+M[p(j)], M[j-1])
+    endfor
+It is also an O(n) solution.
+We can look at our solution to the weighted interval scheduling problem in a more general way to come up with a rough template for designing dynamic programming algorithms. To set about developing an algorithm based on dynamic programming, one need a collection of subproblems derived from the original problem that satisfies a few basic properties:
+ i. There are only a polynomial number of subproblems
+ ii. The solution to the original problem can be easily compute from the solutions to the subproblems.
+ iii. There is a natural ordering on subproblems from smallest to largest together with an easy-to-compute recurrence that allows one to determine the solution to a subproblem from the solutions to some number of subproblems.
+====6.3====
+The weighted-interval problem depends on a binary choice: that is, a given interval would either be included in the final solution or it would not. There are many more complicated problems that we can apply dynamic programming to, where the recurrence will involve "multi-way choices." At each step, we have a polynomial number of possibilities to consider.
+Let's consider trying to find a line of best fit for a given set of data. If the points seem to lie cleanly along one line, we can easily compute the line of best fit. But data is not always so neat. What if we can see that the points would lie best against two or even three lines of best fit? We would then want to formulate a solution that requires us to fit the points well using as few lines as possible; we don't want to just connect each point with its own individual line. The is the "Segmented Least Squares" problem.
+The best running time for the algorithm, as seen in the book, is O(n^2).
+====6.4====
+For problems like the Knapsack problem, we will need to add an additional variable to the recurrence underling the dynamic program. The goal in these kinds of more general problems is to choose a subset of maximum total value, subject to the restriction that its weight not exceed W. A greedy solution that always finds the correct solution to this type of problem is not known, so we must turn to dynamic programming. For this problem, determining a good set of subproblems will be tricky.
+In order to find the value of Opt(n), we need to not only know the value of Opt(n-1), but also we need to know the best solution we can get using a subset of the first n-1 items and total allowed weight W - wn.
+The running time for the algorithm this creates, as seen in the book, is O(nW). Given a table M of the optimal values of the subproblems, the optimal set S can be found in O(n) time.
 ====Readability====
+Dynamic programming is pretty confusing! I had a hard time understanding these sections, especially the final one. The first two were pretty clear. 5/10 overall, though.
+=====Summary of 7.1-7.2, 7.5, 7.7=====
+====7.1====
+Graphs are often used to model transportation networks, where edges carry some sort of traffic and nodes act as "switches" passing traffic between different edges. Network models like this have capacities on the edges and source nodes in the graph (that generate traffic) and sink nodes in the graph that are destinations that absorb traffic as it arrives. The traffics across these kinds of graphs is often referred to as "flow."
+A typical goal with this type of graph is to arrange the traffic so as to make as efficient use as possible of the available capacity. At the moment, there is no known algorithm for the Maximum-Flow Problem that could be considered a "dynamic programming" solution, so we'll return to greedy solutions.
+The Ford-Fulkerson Algorithm solves this problem. (page 344)
+It can be implemented in O(mC) time, so long as all the capacities in the flow network are integers.
+====7.2====
+We will continue to analyze the Ford-Fulkerson algorithm and verify that it does indeed have the maximum possible value for any graph G.
+The Ford-Fulkerson algorithm terminates when the flow f has no s-t path in the residual graph of Gf. This turns out to be the only property needed for proving its maximality. (7.9, pg 348)
+Remember when we pointed out that capacities in our graph must be integers for the F-F algorithm? Well, if that's NOT the case, then it is entirely possible for the algorithm to run forever, if real numbers are incorporated.
+====7.5====
+The Bipartite Matching Problem
+A matching in a graph G is a subset of the edges M in E such that each node appears in at most one edge in M. The Bipartite Matching problem is that of finding a matching in G of largest possible size.
+The Ford-Fulkerson algorithms can be used to find a maximum matching in a bipartite graph in O(mn) time.
+====7.7====
+Much of the power of the Maximum-Flow Problem lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph.
+Before, we had just one sink and one source. Now, we will have multiple! Now, instead of maximizing flow value, we will have sources that have a fixed supply and sinks that have a fixed demand, and our goal is to ship flow from nodes with available supply to those with given demands.
+====Readability====
+/10. This section is incredibly dense and hard to make sense of. I don't think the book does a great job of explaining overly technical aspects.