Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2014:journals:gabi:home [2014/03/26 00:30] – [Chapter 5.5] tremog | courses:cs211:winter2014:journals:gabi:home [2014/04/02 01:21] (current) – [Chapter 7.7] tremog | ||
---|---|---|---|
Line 1566: | Line 1566: | ||
===== Chapter 6 ===== | ===== Chapter 6 ===== | ||
==== Chapter 6.1 ==== | ==== Chapter 6.1 ==== | ||
+ | |||
+ | //**6.1: Weighted Interval Scheduling: A Recursive Procedure **// | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | *// | ||
+ | |||
+ | Basically, we've done part of this before. We know how to set up a greedy algorithm to say that we want the maximum number of jobs. But now we don't want to only worry about time but also account in for weights-- like monetary amounts for each job. So before when each job had a value of 1, equal across the board. Now it's different! | ||
+ | |||
+ | Switch to dynamic programming!! | ||
+ | |||
+ | We want to split this into two outcomes. Take job j. When computing the optimal value of the solution, you can either include job j or exclude job j, depending on the maximum value that would result from that choice. | ||
+ | |||
+ | Through dynamic programming, | ||
+ | |||
+ | We continue to compute down the branches of the algorithm until we get to Compute-Opt(0) then we use this info to solve the rest of the problem. We can do this by solving one instance of the problem and then saving the results to use in the recursion. This is memoizing. | ||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | alg: Compute-Opt(j) p254 | ||
+ | |||
+ | -> | ||
+ | |||
+ | alg: M-Compute-Opt(j) p256 | ||
+ | |||
+ | -> Runtime: ???? | ||
+ | |||
+ | alg: FindSoln(j) p258 | ||
+ | |||
+ | -> Runtime: O(n) | ||
+ | |||
+ | |||
+ | **Questions: | ||
+ | |||
+ | Does running these separate algorithms impact runtime of the total solution or is this negligible or unnessicary to consider?? | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | Dynamic programming. Or rather the definition. This was something I sort of picked up in class on Friday and kind of //got it// more. | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | Greedy solutions won't work here. Something else must be tried. Also you need to memoize!!!! | ||
+ | |||
+ | **Readability (scale: 1-10): | ||
+ | |||
+ | 8-9. Super clear. Very fast. Well organized. | ||
+ | |||
==== Chapter 6.2 ==== | ==== Chapter 6.2 ==== | ||
+ | |||
+ | //**6.2: Principles of Dynamic Programming**// | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | In order to fully compute the value and the elements involved in the solution we have to MEMOIZE! However once we save all of these things in a memoized array, how do we get them out?? | ||
+ | |||
+ | Dealing with the iterative execution of the Weighted Scheduling problem is better because it runs for n iterations and spends constant time in each. | ||
+ | |||
+ | We can iterate!! | ||
+ | |||
+ | To set up an algorithm for this, we need a collection of sub problems that satisfy a few properties: | ||
+ | |||
+ | * -> There are only a polynomial numbers of subproblems | ||
+ | * -> The solution to the original problem can e easily computed from the solutions to the subproblems. | ||
+ | * -> There is a natural ordering on subproblems from " | ||
+ | |||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | alg: Iterative-Compute-Opt p259 | ||
+ | |||
+ | -> Runtime: O(n) | ||
+ | |||
+ | **Questions: | ||
+ | |||
+ | If you can't order them, how do you do it? Is there a separate algorithm. | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | There are three things that your subproblems have to follow in order for this to work with them. | ||
+ | |||
+ | **Readability (scale: 1-10): | ||
+ | |||
+ | 8. Complex, but super short. I like it. | ||
+ | |||
==== Chapter 6.3 ==== | ==== Chapter 6.3 ==== | ||
+ | |||
+ | //**6.3: Segmented Least Squares: Multi-Way Choices**// | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | Our goal is, given points on graph in a general curve, make a line or set of lines with which will characterize the curve best. For this we need to delve into the realm of " | ||
+ | |||
+ | Now, it would be great to just add a great number of line segments to make up the line. But we want to do this with the least number of line segments that maximizes the correction of the solution with the least amount of penalty. How do we do this? | ||
+ | |||
+ | The penalty of a partition is the sum of the following terms: | ||
+ | |||
+ | * -> the number of segments, times a fixed given multiplier C > 0 | ||
+ | * -> for each segement, the error value of the optimal lines through the segment | ||
+ | |||
+ | |||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | alg: Segemented-Least-Squares (n) p265 | ||
+ | |||
+ | -> Runtime: O(n^2) | ||
+ | |||
+ | * -> Array M[0....n] | ||
+ | * -> Set M[0] = 0 | ||
+ | * -> For all pairs i <= j | ||
+ | * -> -> Compute the least squares error e(i,j) for each segment pi....pj | ||
+ | * -> End For | ||
+ | * -> For j = 1,2,....n | ||
+ | * -> -> Use the recurrence (6.7) to compute M[j] | ||
+ | * -> End for | ||
+ | * -> Return M[n] | ||
+ | |||
+ | alg: Fine-Segements(j) p266 | ||
+ | |||
+ | -> Runtime: O(n^2) | ||
+ | |||
+ | **Questions: | ||
+ | |||
+ | I don't completely understand what this is or why this is. Nor to I really understand in what context this would be useful. So this really hurts my understanding of this section. | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | The explanation in class was much much better for me. This was jumbled and kind of lost me. | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | You can't just make all of the lines (no infiinite lines). There is cost associated with them. | ||
+ | |||
+ | **Readability (scale: 1-10): | ||
+ | |||
+ | 6? It's overall score is wounded by the fact that I really dont understand this problem too much :/ | ||
+ | |||
==== Chapter 6.4 ==== | ==== Chapter 6.4 ==== | ||
+ | |||
+ | //**6.4: Subset Sums and Knapsacks: Adding a variable**// | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | With the subset sums and the knapsack problems, we are looking at something close to the interval jobs problem. Additionally, | ||
+ | |||
+ | "We have to come up with a small number of subproblems so that each subproblem can be obtained easily once we know the solutions to all the subproblems." | ||
+ | |||
+ | Our final outcome ends up being: | ||
+ | |||
+ | (6.8) If w < w1 then OPT(i,w) = OPT(i - 1, w) Otherwise, OPT(i,w) = Max(opt(i-1, | ||
+ | |||
+ | Just like with the interval problem, in the knapsack problem, we are looking at if we INCLUDE an item or not including an item. These are the two outcomes. And, just like before, we want to design an algorithm that is going to build up a set of all of these OPt(i,w) values while computing them-- AT MOST-- once. | ||
+ | |||
+ | Determining the subset of the sum is O(nW) time-- weird! | ||
+ | |||
+ | This runtime is not a polynomial function of nl but rather, it is a polynomial function of n and W, w being the largest integer involved in defining the problem. This makes this problem " | ||
+ | |||
+ | (6.10) Given a table M of the optimal values of the subproblems, | ||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | alg: Subset-Sum(n, | ||
+ | |||
+ | -> Runtime: O(nW) | ||
+ | |||
+ | alg: Knapsack Problem p271 | ||
+ | |||
+ | -> Runtime: O(nW) | ||
+ | |||
+ | |||
+ | **Questions: | ||
+ | |||
+ | So the list being used in these algorithms isn't a memoized array, but rather a two-d memoized array? Because of the "excel sheet" kind of layout? | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | The runtime of nW and what it means. In class that kind of threw me for a loop. I got it at the end of class, but the actual reading of it here (and how it is pseudo-poly made more sense reading it a second time. | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | "We have to come up with a small number of subproblems so that each subproblem can be obtained easily once we know the solutions to all the subproblems." | ||
+ | |||
+ | This runtime is not a polynomial function of nl but rather, it is a polynomial function of n and W, w being the largest integer involved in defining the problem. This makes this problem " | ||
+ | |||
+ | **Readability (scale: 1-10): | ||
+ | |||
+ | 8. Super clear. Very easy to read. I like how it introduced kind of the way that the algorithm worked under the skin and then gave kind of a real example of it. With some of these algorithms, it can be hard to give it an " | ||
+ | |||
+ | ===== Chapter 7 ===== | ||
+ | ==== Chapter 7.1 ==== | ||
+ | |||
+ | //**7.1: The Mazimum-Flow Problem and the Ford-Fulkerson Algorithm**// | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | One often uses graphs to model // | ||
+ | |||
+ | For example, think of a highway. The edges are the roads of the highway and the nodes are the interchanges. | ||
+ | |||
+ | Networks of this type have a few different characteristics. One, there are CAPACITIES to the edges, namely how much " | ||
+ | |||
+ | So now that we have the structure of this data, we want to know how to use it. Specifically, | ||
+ | |||
+ | We are going to frame this in two graphs: the one we are looking at and then a " | ||
+ | |||
+ | Given a flow network G, and a flow f on G, we define the residual graph Gf of G with respect to f as follows: | ||
+ | |||
+ | -> the node set Gf is same of that as G | ||
+ | -> for each edge e == (u,v) of G on which F(e) < ce there are ce - f(e) " | ||
+ | |||
+ | The algorithm we are using is called the Ford-Fulkerson algorithm. And it terminates in at most C iterations of the While loop. | ||
+ | |||
+ | Thus, the F-F algorithm can be implemented in O(mC) time!!! | ||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | p343: Augmenting Paths in a Residual Graph | ||
+ | |||
+ | -> Runtime: O(mC) | ||
+ | |||
+ | augment(f, P): | ||
+ | * -> Let b = bottleneck(P, | ||
+ | * -> For each edge 9u,v) in P | ||
+ | * -> -> If e == (u,v) is a forward edge then increase f(e) in G by b | ||
+ | * -> -> Else (u,v) is a backward edge, and let e = (v,u) | ||
+ | * -> | ||
+ | * ->-> Endif | ||
+ | * -> Endfor | ||
+ | * -> Return(f) | ||
+ | |||
+ | p344: Max-Flow | ||
+ | |||
+ | -> Runtime: O(mC) | ||
+ | |||
+ | MaxFlow() | ||
+ | * -> Initially f(e) = 0 for all e in G | ||
+ | * -> While there is an s-t path in the residual graph G | ||
+ | * ->-> Let P be a simple s-t path in Gf | ||
+ | * ->-> f' = augment(f, | ||
+ | * ->-> Update f to be f' | ||
+ | * ->-> Update the residual graph Gf to be Gf' | ||
+ | * -> Endwhile | ||
+ | * -> Return f | ||
+ | |||
+ | **Questions: | ||
+ | |||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | The idea that a residual graph is a separate graph. I think because in class we were only working with the one graph with the animations I thought it was the same one. This cleared things up. | ||
+ | |||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | Networks of this type have a few different characteristics. One, there are CAPACITIES to the edges, namely how much " | ||
+ | |||
+ | **Readability (scale: 1-10): | ||
+ | |||
+ | 7. Pretty clear in some parts. Could be cloudy in others | ||
+ | ==== Chapter 7.2 ==== | ||
+ | |||
+ | //**7.2: Maximum Flows and Minimum Cuts in a Network**// | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | Our goal is to go ahead and show that the flow that is returned by the F-F algorithm has the maximum flow possible of any other flow in G. How do we check this??? We want to look at the way in which the structure of the flow network places upper bounds on the max value of s-t flow. | ||
+ | |||
+ | We already have one bound: the value of v(f) of any s-t flow. That, at most, is C = SUM (e out of s Ce) | ||
+ | |||
+ | (7.6) Let f be any s-t flow and (A,B) any s-t cut. Then v(f) = f(out(A)) - F(in(A)) | ||
+ | |||
+ | (7.8) Let f be any s-t flow, and (A,b) any s-t cut. Then v(f) < = c(A,B) | ||
+ | |||
+ | In a sense, (7.8) looks weaker than (7.6) does since it is only an inequality rather can than equality. However, this becomes extremely useful for us, since the right-hand side is independent of any particular flow f. | ||
+ | |||
+ | Basically, what (7.8) is saying is that //the value of every flow is upper-bounded by the capacity of every cut// | ||
+ | |||
+ | (7.13) In Every flow network the max value of an s-t flow is equal to the minimum capacity of an s-t cut. | ||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | none | ||
+ | |||
+ | **Questions: | ||
+ | |||
+ | What did I just read? That seems like a weird question but I'm slightly confused because I feel like I just read myself in circles. | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | Very very little. | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | In a sense, (7.8) looks weaker than (7.6) does since it is only an inequality rather can than equality. However, this becomes extremely useful for us, since the right-hand side is independent of any particular flow f. | ||
+ | |||
+ | Readability (scale: 1-10): | ||
+ | |||
+ | 5-6. I don't know. This section was very circuitous for me. It could be just that the entire chapter seemed to make very similar points the entire way around it or it could be that I have a hard time reading sums? I don't know. I just got lost and am still very confused as to what I just read. | ||
+ | ==== Chapter 7.5 ==== | ||
+ | |||
+ | //**7.5: A First Application: | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | One of our original goals in developing the Max-Flow problem was to be able to solve the Bipartite Matching problem. | ||
+ | |||
+ | The graph defining a matching problem is undirected, while flow networks are direction. However this is not difficult to implement to find a max matching solution. | ||
+ | |||
+ | We start by computing a max s-t flow in the network G'. We discover that the value of this maximum is equal to the size of the maximum matching in G. Also, our analysis shows that we can actually use the flow itself to recover the matching. | ||
+ | |||
+ | We do this by looking at three facts about M', which is the set of edges of the form (x,y) on which the flow value is one. | ||
+ | |||
+ | 1) M' contains k edges | ||
+ | 2) Each node in X is the nail of at most one edge in M' | ||
+ | 3) Each node in Y is the head of at most one edge in M' | ||
+ | |||
+ | Combining these facts we can see that if we view M' as a set of edges in the original bipartite graph G, we get a matching of size k. In short: | ||
+ | |||
+ | (7.37) The size of the maximum matching in G is equal to the value of the max flow in G' and the edges in such matching in G are the edges that carry flow from X to Y in G' | ||
+ | |||
+ | |||
+ | Moreover, we can do all of this in O(Mc) time since we are using the F-F algorithm!!! | ||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | the Ford-Fulkerson algorithm, which is actually discussed in section 1. | ||
+ | |||
+ | **Questions: | ||
+ | |||
+ | Why couldn' | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | The runtime!! (It's the same as section one ;) ) | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | The graph defining a matching problem is undirected, while flow networks are direction. However this is not difficult to implement to find a max matching solution. | ||
+ | |||
+ | **Readability (1-10):** | ||
+ | |||
+ | 7. Would have been an 8 if there was some psudeo-code to go along with it. The psudeo-code always helps me sort through the text (since the texbook can be a little bit dense sometimes. The code is a nice outline) | ||
+ | ==== Chapter 7.7 ==== | ||
+ | |||
+ | //**7.7: Extensions to the Max-Flow Problem**// | ||
+ | |||
+ | **Summary: | ||
+ | |||
+ | Many issues that can be solved with the Max-Flow problem have essentially nothing to do with the fact that it models traffic in a network. Who knew? It also helps with problems that have nontrivial combinatorial search components. It is very useful because it can be solved in poly-time with O(Mc) time because of the F-F algorithm. | ||
+ | |||
+ | One of these problems is the : | ||
+ | |||
+ | (7:51) The Graph G has a feasible circulation with demands (dv) if and only if for all cuts (A,B) | ||
+ | |||
+ | |||
+ | If all of the capacities and demands in G are integers and there is a feasible circulation, | ||
+ | |||
+ | |||
+ | **Algorithms: | ||
+ | |||
+ | Once again, the F-F algorithm from section one. | ||
+ | |||
+ | |||
+ | **Questions: | ||
+ | |||
+ | Where is the psudo-code? :( | ||
+ | |||
+ | **What made sense?:** | ||
+ | |||
+ | The real world application. I don't know why but I can visualize this problem well. Maybe not real world, but this is much less of an abstraction than the ones in 7.5 and 7.2 | ||
+ | |||
+ | **Key Points:** | ||
+ | |||
+ | Many issues that can be solved with the Max-Flow problem have essentially nothing to do with the fact that it models traffic in a network. Who knew? | ||
+ | |||
+ | **Readability (1-10):** | ||
+ | |||
+ | 7. No psudeo-code :( | ||
+ | |||
+ | |||
+ |