Differences

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

--- courses:cs211:winter2014:journals:maggie:home [2014/03/12 02:34] – [5.4 Finding the Closet Pair of Points] weatherlym
+++ courses:cs211:winter2014:journals:maggie:home [2014/04/01 23:11] (current) – [7.6 Disjoint Paths in Directed and Undirected Graphs] weatherlym
@@ Line 318: / Line 318: @@
   * Given n points in the plane, find the pair that is closet together, it is immediately clear that there is an O(n^2) solution - compute the distance between each pair of points and take the minimum,
   * so lets first assume that no two points in the plane have the sam x-coordinate or the same y-coordinate, so we add line L that splits the plane in half, we do this by sorting the the points by their x-coordinates and finding the middle, then we will divide and conquer like in Mergesort:, we find the closet pair among the points in the left half of the plane and the closet pair among the pionts in the right half of the plane, and then we use this information to get the overall solution in linear time
-  * the last combining phase of the algorithm is to find the distances between a point in the left half and a point in the right half of the plane and that this distance may be less than any other distance in either side
+  * the last combining phase of the algorithm is to find the distances between a point in the left half and a point in the right half of the plane and that this distance may be less than any other distance in either side, to find the minimum distance between a point on the left and a point on the right can be found on pg 228 and the proof on pg 229
-  *
+  * the summary of the algorithm can be found on page 230 and the algorithm has a runtime of O(nlogn)
+====== 6.1 Weighted Interval Scheduling: A Recursive Procedure ======
+  * Let's suppose that the requests are sorted in order of nondecreasing finish time, we'll say a request i comes before a request j if i < j, we define p(j), for an interval j, to be the largest index i < j such that intervals i and j are disjoint, we define p(j) = 0 if no request i < j is disjoint from j
+  * For the optimal solution Oj on {1, 2, ..., j} our reasoning says either j is in Oj in which case OPT(j) = value of j + OPT(p(j)), or j is not in Oj in which the case is OPT(j) = OPT(j-1), since these are the only two possibles choices we can say that OPT(j) = max{vj + OPT(p(j)), OPT(j-1)} and so j belongs to an optimal solution on the set {1, 2, ...,j} if and only if vj + OPT(p(j)) >= OPT(j-1)
+Compute-Opt(j):
+    If j = 0
+        Return 0
+    Else
+        Return max(vj + Compute-Opt(p(j)), Compute-Opt(j-1))
+  * Compute-Opt(j) correctly computes OPT(j) for each j = 1, 2, ..., n
+Memoizing the Recursion
+  * the code aboves runs in exponential time as written is simply due ot the spectacular redundancy in the number of times it issues each of these calls, to eliminate the redundancy, we could store the value of Compute-Opt in a globally accessible place, the first time we compute it and then simply use this value in place of all future recursive calls, this technique is called memoization
+  * for this procedure we will make use of an array M[0...n]; M[j] will start with the value empty but will hold the value of Compute-Opt(j) as soon as it is first determined, to determine OPT(n), we call M-Compute-Opt(n)
+M-Compute-Opt(j)
+    If j = 0
+        Return 0
+    If M[j] is not empty
+        Return M[j]
+    else
+        Define M[j] = max(vj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
+            Return M[j]
+  * The running time of M-Compute-Opt(n) is O(n) assuming the intervals are sorted by their finish times
+  * Computing a solution in Addition to ITs Value, we will trace back through the array M to find the set of intervals in an optimal solution
+Find-Solution(j)
+    If j = 0
+        Output Nothing
+    Else
+        If vj + M[p(j)] >= M[j-1]
+            Output j together with the result of Find-Solution(p(j))
+        Else
+            Output the result of Find-Solution(j-1)
+  * Given the array M of the optimal values of the sub-problems, Find-Solution returns an optimal solution in O(n) time
+====== 6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems ======
+  * we can directly compute the entries in M by an iterative algorithm, rather than using memoized recursion, we just start with M[0] = 0 and keep incrementing j
+Iterative-Compute-Opt
+    M[0] = 0
+    For j from 1 to n
+        M[j] = max(vj + M[p(j)], M[j-1])
+  * this algorithm write OPT(j) in array entry M[j], we can pass the filled-in array M to Find-Solution to get an optimal solution in addition to the value, finally running time of Iterative-Compute-Opt is clearly O(n) since it explicitly runs for n iterations and spends constant time on each
+  * this provides a second efficient algorithm to solve the Weighted Interval Scheduling Problem
+A Basic Outline of Dynamic Programming
+  * iterative building up of subproblems, to set about developing an algorithm based on dynamic programming, one needs a collection of subproblems derived from the original problem that satisfies a few basic propterties
+  - There are only a polynomial number of subproblems
+  - The solution to the original problem can be easily computed from teh solutions to the subproblems
+  - there is a natural ordering on subproblems from smallest to largest, together with an easy-to-compute recurrence that allows one to determien the solution to a subproblem from the solutions to some number of smaller subproblems
+====== 6.3 Segmented Least Squares: Multi-way Choices ======
+  * multi-way choices - at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution
+  * plotted on a two-dimensional set of axes, one tries to pass a line of best fit through the data, find the line with the minimum error y = ax + b where a and b are defined on page 262
+  * given a set of points where each x value is unique, we must partition P into some number of segments where P is the set of points, each segment is a subset of P that represents a contiguous set of x-coordinates, for each segment S in our partition of P we compute the line minimizing the error with respect to the points in S
+  * the penalty of a partition is defined by the sum of the following terms
+  *   * the number of segments into which we partition P, times a fixed given multiplier c > 0
+  *   * for each segment, the error value of the optimal line through that segment
+  * our goal is to find a partition of minimum penalty
+  * let OPT(i) denote the optimum solution for the points p1,...,pn and let eij denote the minimum error of any line with repect to pi, pi+1,...,pj
+  * If the last segment fo the optimal partition is pi,...,pn, then the value of the optimal solution is OPT(n) = ein + C + OPT(i-1)
+  * For the subproblem on the points p1,...,pj, OPT(j) = min from i = 1 to j (eij + C + OPT(i-1)), and the segment pi,...,pj is used as an optimum solution for the subproblem if and only if the minimum is obtained using index i
+Segmented-Least-Squares(n)
+     Array M[0...n]
+     Set M[0] = 0
+     For all pairs i <= j
+          Compute the least squares error eij for the segment pi,...pj
+     For j = 1,...n
+          Use the recurrence OPT(j) = min from i = 1 to j (eij + C + OPT(i-1)) to compute M[j]
+     Return M[n]
+FindSegments(j)
+     If j = 0
+          output nothing
+     Else
+          Find an i that minimizes eij + C + M[i-1]
+          Output the segment {pi,...,pj} and the result of Find-Segments(i-1)
+  * Analyzing the Runtime - first we need to compute the values of all the least-squares errors eij, and to perform this there are O(n^2) pairs (i,j) for which this computation is needed and for each pair we can use the formula given at the begining of the section in O(n) time, giving us O(n^3) for computing the eij error values.  Following this the algorithm has n iterations, and for each j we need to determine the minimum in the recurrence which takes time O(n), giving a running time of O(n^2) once all the eij values have been determined
+====== 6.4 Subset Sums and Knapsacks: Adding a Variable ======
+  * in this scheduling problem, we have a single machine that can process jobs and a set of requests, we are only able to use this resource for the period between time 0 and time W, for some number W,
+  * for the knapsack problem, where each request i has both a value vi, and a weight wi, the goal in this problem is to select a subset of maximum total value, subject to the restriction that its total weight not exceed W
+  * We will use OPT(i, w) to denote the value of the optimal solution using a subset of the items {1,...,i} with maximum allowed weight w, that is OPT(i, w) = maximum over subsets S of {1, ..., i} that satisfy the Summation of j in S where wj <= w
+  * If n is not in the optimum solution, then OPT(n, W) = OPT(n-1, W), since we can simply ignore item n
+  * If n is in the optimum solution, then OPT(n, W) = wn + OPT(n-1, W-wn) wince we now seek to use the remaining capacity of W - wn in an optimal way across items 1, 2, ..., n-1
+  * If w < wi then OPT(i, w) = OPT(i-1, w), otherwise OPT(i, w) = max(OPT(i-1, w), wi + OPT(i-1, w-wi))
+Subset-Sum(n, W)
+     Array M[0...n, 0....W]
+     Initialize M[0,w] = 0 for each w = 0,1,...W
+     For i = 1,..n
+          For w = 0,...,W
+               Use the recurrence If w < wi then OPT(i, w) = OPT(i-1, w), otherwise
+               OPT(i, w) = max(OPT(i-1, w), wi + OPT(i-1, w-wi)) to compute M[i,w]
+     Return M[n, W]
+  * for the algorithm we've just designed, we  need a two-dimensional table, reflecting the two-dimensional array of subproblems that is being built up
+  * The Subset-Sum(n, W) algorithm correctly coputes the optimal value of the problem, and runs in O(nW) time
+  * Given a table M of the optimal values of the subproblems, the optimal set S can be found in O(n) time
+====== 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ======
+  * Consider a highway system in which the edges are highways and the nodes are interchanges, network models of this type have several ingredients: capacities on the edges indicating how much they can carry; source nodes in the graph which generate traffic; and sink nodes in the graph which absorb traffic as it arrives, and the traffic itself which is transmitted across the edges
+  * We'll refer to the traffic as flow - an abstract entity  that is generated at source nodes, transmitted across edges, and absorbed at sink nodes
+  * flow network is a directed graph G = (V, E) where each edge e is a capacity, which is a nonnegative number denoted ce, there is a single source s in V, and a single sink t in V
+  * we will say that an s-t flow is a function f that maps each edge e to a nonnegative real number where the value f(e) represents the amount of flow carried by edge e
+  * For a flow f, each e in E, we have 0 <= f(e) <=ce, and for each node v other than s and t, we have the sum for all edges e into v, f(e) equals the sum of all edges e out of v f(e)
+  * Given a flow network, the goal is to arrange the traffic so as to make as efficient use as possible of the available capacity
+  *
+====== 7.2 Maximum Flows and Minimum Cuts in a Network ======
+  * we say that an s-t cut is a partition (A, B) of the vertex set V so that s is in A and t is in B
+  * the capacity of a cut (A, B), which we will denote c(A, B) is simply the sum of the capacities of all edges out of A
+  * cuts provide very natural upper bounds on the values of flows
+  * Let f be any s-t flow, and (A, B) any s-t cut, then v(f) = f out (A) - f in (A), this statement says that by watching the amount of flow f sends across a cut, we can exactly measure the flow value, it is the total amount that leaves A, minus the amount that "swirls back" into A
+  * (7.8) Let f be any s-t flow, and (A, B) any s-t cut, then v(f) <= c(A, B)
+  * Let f bar denote the flow that is returned by the Ford-Fulkerson Algorithm, we want to show that f bar has the maximum possible value of any flow in G
+  * If f is an s-t flow s.t. there is no s-t path in the residual graph Gf, then there is an s-t cut (A*, B*) in G for which v(f) = c(A*, B*). Consequently f has the maximum value of any flow in G, and (A*, B*) has the minimum capacity of any s-t cut in G
+  * The flow f bar returned by the Ford-Fulkerson Algorithm is a maximum flow
+  * Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time
+  * The point is that f must be a maximum s-t flow for if there were a flow f' of greater value, the value of f' would exceed the capacity of (A, B), and this would contradict (7.8).  Similarly, it follows that (A, B) is a minimum cut - no other cut can have a smaller capacity, for if there were a cut (A', B') of smaller capacity, it would be less than the value of f, and this again would contradict (7.8), so this gives us the Max-Flow Min-Cut Theorem - In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut
+  * If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer
+====== 7.5 A First Application: The Bipartite Matching Problem ======
+  * Beginning with the graph G in an instance of the Bipartite Matching, we construct a flow network G', first we direct al edges in G from X to Y, we then add a node s and an edge (s,x) from s to each node in X.  We add a node t, and an edge (y, t) from each node in Y to t.  Finally, we give each edge in G' a capacity of 1, we now compute a maximum s-t flow in this network G'
+  * The size of the maximum matching in G is equal to the value of the maximum flow in G'; and the edges in such a matching in G are the edges that carry flow from X to Y in G'
+  * The Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time, where m is the number of edges
+  * We can decide if the graph G has a perfect matching by checking if the maximum flow in a related graph G' has value at least n, by the Max-Flow Min-Cut theorem there will be an s-t cut of capacity less than n if the maximum -flow value in G' has value less than n
+  * If there are nodes x1 and x2 in X that have only one incident edge each, and the other end of each edge is the same node y, then clearly the graph has no perfect matching
+  * Assume that the bipartite graph G = (V, E) has two sides X and Y st the size of X is equal to the size of Y.  Then the graph G either has a perfect matching or there is a subset A of X st the size of Gamm(A) < the size of A where Gamm(A) is a subset of Y and denotes the set of all nodes that ar adjacent to nodes in A.  A perfect matching can be found in O(mn) time
+====== 7.6 Disjoint Paths in Directed and Undirected Graphs ======
+  * We say that a set of paths is edge-disjoint if no two paths share an edge,
+  * Given a directed graph G = (V, E) with two distinguished nodes s, t in V, the Directed Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in G
+  * The Undirected Edge-Disjoint Paths Problem is to find the maximum number of edge-disjoint s-t paths in an undirected graph G
+  * Both directed and the undirected versions of the problem can be solved using flows, starting with the directed problem, given the graph G = (V, E) we define a flow network in which s and t are the source and sink, and with capacity of 1 on each edge, suppose there are k edge-disjoint s-t paths, we can make each of these carry one unit of flow.  If there are k edge-disjoint paths in a directed graph G from s to t, then the value of the maximum s-t flow in G is at least k
+  * If f is a 0-1 valued flow of value v, then the set of edges with flow value f(e) = 1 contains a set of v edge-disjoint paths
+  * There are k edge-disjoint paths in a directed graph G from s to t if and only if het value of the maximum value of an s-t flow in G is at least k
+  * The Ford-Fulkerson Algorithm can be used to find a maximum set of edge-disjoint s-t paths in a directed graph G in O(mn) time
+  * In every directed graph with nodes s and t, the maximum number of edge-disjoint s-t paths is equal to the number of edges whose removal separates s from t
+  * There are k edge-disjoint paths in an undirected graph G from s to to if and only if the maximum value of an s-t flow in the directed version G' of G is at least k.  The Ford-Fulkerson Algorithm can be used to find a maximum set of disjoint s-t paths in an undirected graph G in O(mn) time
+  * In every undirected graph with nodes s and t, the maximum umber of edge-disjoint s-t paths is equal to the minimum number of edges whose removal separates s from t.