Differences

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

--- courses:cs211:winter2012:journals:joey:home [2012/03/28 05:14] – [Chapter 6 - Dynamic Programming] brownjn
+++ courses:cs211:winter2012:journals:joey:home [2012/04/04 04:31] (current) – [Chapter 7 - Network Flow] brownjn
@@ Line 207: / Line 207: @@
 We need to memoize the solution through Recursion. Memoization is the technique of saving values that have already been computed. The Memoized algorithm can be found on pg 256. It is basically the same as the above algorithm, but results are stored in an array rather than computed on each recursion step. In this algorithm, there can be at most O(n) calls, therefore, the algorithm is O(n). This will give an array filled with the optimal solutions of the sub-problems, and an optimal array can be found from this sub-problem in O(n) time.
+== 6.2 - Principles of Dynamic Programming: Memoization or Iteration over Sub-problems ==
+The way we solved the previous problem was to make an exponential recursive problem and then memoize it so that it takes only O(n) time instead of O(n^2) time.
+When designing the algorithm, the key to efficiency is the array M. Once that array is filled, it is trivial to find the optimal solution. The algorithm to find the optimal solution is on pg 259.
+== 6.3 Segmented Least Squares: Multi-way Choice ==
+This has to do with the line of best fit through a piece of scientific or statistical data. The line which has the minimum error can be found with calculus. Now what if the data requires a number of line segments. Our problem is this: we need to formulate an algorithm that identifies a few points in the sequence at which a discrete change occurs (from one segment to another).
+For this problem:
+OPT(j) = minimum cost for points p1, pi+1 , … , pj
+e(i, j) = minimum sum of squares for points pi, pi+1 , …, pj
+To compute the problem:
+Last segment contains points pi, pi+1, … , pj for some i
+Cost = e(i, j) + c + OPT(i-1)
+The recurrence is Opt(j) = min(e[i,j] + C + Opt(i-1)).
+The algorithm for this problem is on pg 265.
+== 6.4 Subset Sums and Knapsacks: Adding a variable ==
+The knapsack problem is when we have a collection of items with weights and values. The goal is to fill the knapsack with items of maximum value, but is restricted by a weight limit.
+Basically,
+If w<w[i] then OPT(i, w) = OPT(i-1, w). Otherwise
+OPT(i,w) = max(OPT(i-1, w), v[i] + OPT(i-1, w-w[i])
+Interest: 7
+Readability: 5, I think the lectures helped the most with this section compared to the others (maybe not 5... that was difficult to get through as well).
+====== Chapter 7 - Network Flow ======
+**7.0 - Introduction**
+Matchings in bipartite graphs can model situations in which objects are being assigned to other objects. One natural example is when the nodes in X represent jobs and the nodes in Y represent machines. A perfect matching is a way of assigning each job to a machine that can possess it, with the property that each machine is assigned exactly one job. To create a Bipartite Matching algorithm, we will develop network flow algorithms and then look at the bipartite graph as a special case. The algorithms will be applicable to a host of other problems as well.
+**7.1 - The Maximum-Flow Problem and the Ford-Fulkerson Algorithm**
+The problem: Consider a network where the nodes are switches, and the directed edges have capacities. Source nodes in this graph create traffic, and sink nodes absorb traffic. The traffic across this graph will be called flow, and we want to maximize the flow being sent/received. No edges enter the source and no edges leave the sink. In our models, we will only analyze a steady flow of traffic, not bursty traffic. So... given a flow network, how do we arrange the traffic so as to make as efficient use as possible of the available capacity? Or, given a flow network, find a flow of maximum possible value.
+In order to solve this problem, we will use a method that uses a residual graph, whereas we can push flow backwards on edges that already carry flow , to divert it in a different direction. The Ford-Fulkerson Algorithm involves adding flow onto an edge, then checking for bottlenecks, then undoing the flow according to that bottleneck. The algorithm can be found on pg 344 of the text. The complexity of this algorithm is O(n+m) or just O(m).
+**7.2 - Maximum Flows and Minimum Cuts in a Network**
+For this section, we split the graph into two sections, and prove the maximum possible flow for each section. At some point the flow must cross from one section to the other, so if we can be sure that this is optimal, we can ensure that the entire thing is optimal. The value of every flow is upper-bounded by the capacity of every cut.
+In every network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.
+**7.5 - A First Application: The Bipartite Matching Problem**
+In order to solve this one, just add a source node and a sink node, make the current graph directed from one grouping to the other, and then add in the source and sink so that everything flows in the same direction. Then it is as simple as just implementing the Ford-Fulkerson Algorithm on this graph. The algorithm will run in O(mn) time. This will find an a matching of the largest possible size.
+Sometimes there is no perfect matching in a bipartite graph. We can check whether or not a matching is perfect if the flow coming into the sink or leaving the source is 1/2 the size of n.
+**7.7 - Extensions to the Maximum-Flow Problem**
+Imagine the situation in which there are multiple sinks and sources. In this case, instead of max flow, each node has a demand or a supply. In order to solve this problem, again, add a sink and source, or super-sink and super-source. The capacities of the edges going from the super-source to the supply nodes are equal to the supply offered by those nodes; and the edges going from the demand nodes to the super-sink are equal to the demand by those nodes. Then it is just a max flow problem.
+**Interest:** 10 (taking Networks with Stough and this is pretty relevant)
+**Readiblity:** 5 (the language could have been clearer)