Quiz 7
12172010
02:10 AM ET (US)

What about quiz 7?

Yoav Freund
12142010
04:19 PM ET (US)

The cutoffs are: A+ > 95% > A > 84% > A > 78.65% > B+ > 70% > B > 65% > B > 60% > C > 40%

andrew
12132010
08:57 PM ET (US)

Is there a grade distribution for the scores?
i.e. the cutoff for "A", "B", "C","D","F"?

Qian
12092010
03:14 AM ET (US)

Arvine, No. Consider this network, G(V,E),
V = {s,t,a,b} E = {(s,a),(a,t),(a,b),(b,t)} c = 1 for all edges
The size of the max flow is 1. One max flow can be {(s,a),(a,t}}.
Now change the capacity of edge (a,t) to 0. The new max flow is {(s,a),(a,b),(b,t)}, with size 1.

Qian
12092010
03:06 AM ET (US)

FooFunction(): An edge between two nodes corresponding opposite literals (e.g. x and ~x) guarantees that only one of the two will be in the independent set. This corresponds to either x or ~x being TRUE but not both in a satisfying assignment.

Arvine
12092010
02:48 AM ET (US)

Is an edge that has used its full capacity in the network flow necessarily a critical edge, since decrease it will break the "conservation" condition. If not, can someone give a counterexample? Thanks,

Sheng Wang
12092010
02:22 AM ET (US)

If we want to have a solution for 3SAT, we need to convert it into a form solvable by an algorithm that solves Independent Set. Opposite polarity means that the literal will have an edge to another literal that is not its complement, and isn't in its clause in the 3SAT. Once we have the solution for the converted Independent Set input, we can do a polynomial time transformation to come up with the solution for 3SAT. Note that we can call the algorithm for Independent Set as many times as we like in constant time. (Just imagine an oracle that gives a solution in constant time.) You'll have to do the same if you want to reduce 3SAT to Clique. Edited 12092010 02:23 AM

FooFunction()
12092010
02:15 AM ET (US)

For some reason the explanation of 3SAT > Independent both in the book and lecture notes don't seem to make much sense. I'm having an especially difficult time understanding why we "put an edge between any two nodes that correspond to literals of opposite polarity", what does this accomplish?

Yoav Freund
12092010
12:57 AM ET (US)

You need to find a counterexample : a particular graph and starting node such that the shortest path tree found by Dijkstra is NOT an MST for that graph (i.e. there is another spanning tree with smaller total weight). Edited 12092010 12:59 AM

MST dijstra proof
12092010
12:29 AM ET (US)

For problem 5.9 g),
I can't seem to come up with a satisfactory proof for 5.9g), It seems to me that dijkstra's algorithm may find the shortest path tree from a particular origin node, but not an overall MST . Is this a good enough answer?

Yoav Freund
12082010
10:53 PM ET (US)

Matt, you need to do two things: 1) Prove that a graph has an odd length cycle if and only if it cannot be colored with two colors (in a way that there is no edge between nodes of the same color). 2) Find an algorithm to check whether a graph is twocolorable. If the algorithm finds that it is not possible, it will have found the odd length cycle. Edited 12082010 11:01 PM

Matt Kim
12082010
10:23 PM ET (US)

I was trying to solve this problem: How to find an odd cycle in a graph in O(E) time.
Do you think you could give us some advice on how to solve this ?
I am totally lost.

Qian
12082010
08:24 PM ET (US)

Chad, correction to your assumption: edge (u,v) is not necessarily critical. The reduced flow (1) from this edge (or one path from s to t using this edge in the flow) can be sent through a different path. If size of current max flow is F, the new max flow has size either F or F1.
Some directions:
1. To reduce flow f_uv on edge (u,v) to f_uv1 to satisfy the new capacity constrain, you need to reduce the flow by 1 along a path from s to t in the current max flow. How do you find such a path? 2. After 1, you end up with a new flow. Can you go from here and find the max flow? Can 1 and 2 be done in linear time?

Chad
12082010
07:58 PM ET (US)

So, my study partner and I have been looking into question 7.22 and we were wondering if we could get some direction. So far our solution is the following: Basis of solution: We assume that if the edge (u,v) is critical, then the (new Max Flow = previous  1), and if the edge (u,v) is Not critical, then the (new Max Flow = previousMaxFlow) Assumed Input, Residual Graph G^T as a result of FordFulkerson Assumed Output, the new Max Flow of the altered original Graph. Fe = flow across edge e Se = surplus across edge e CRITe = list of potential Critical edges = every edge e in E initially Do DFS on Residual Graph. if Se = 0 remove e from CRITe else if e == back edge remove e from CRITe else if e == forward edge to vertex, v go to vertex v, and remove attached edge from CRITe to v that was not the forward edge return CRITe if considered edge is within CRITe newMaxFlow = previousMaxFlow  1 else newMaxFlow = previousMaxFlow We are pretty certain that this is wrong, but we wanted to show that we had at least tried to work on it before asking for help. Edited 12082010 08:00 PM

Online version pages
12082010
07:45 PM ET (US)

Does anyone knows the reading page for chapter 8 of the online version text book?

Yoav Freund
12082010
12:02 PM ET (US)

Andy, it is not always possible to increase the maximal flow by changing the capacity of a single edge. For example, consider a graph s>a>b>t where all of the edges have capacity 1. The max flow is 1 and in order to increase it the capacity of *all* edges has to be increased.
