top bar
QuickTopic free message boards logo
Skip to Messages


CSE101, Fall 2010

^     All messages            182-197 of 197  166-181 >>
Quiz 7
02:10 AM ET (US)
What about quiz 7?
Yoav FreundPerson was signed in when posted
04:19 PM ET (US)
The cutoffs are:
A+ > 95% > A > 84% > A- > 78.65% > B+ > 70% > B > 65% > B- > 60% > C > 40%
08:57 PM ET (US)
Is there a grade distribution for the scores?

i.e. the cutoff for "A", "B", "C","D","F"?
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.
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.
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 WangPerson was signed in when posted
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 12-09-2010 02:23 AM
FooFunction()Person was signed in when posted
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 FreundPerson was signed in when posted
12:57 AM ET (US)
You need to find a counter-example : 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 12-09-2010 12:59 AM
MST dijstra proof
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 FreundPerson was signed in when posted
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 two-colorable. If the algorithm finds that it is not possible, it will have found the odd length cycle.
Edited 12-08-2010 11:01 PM
Matt Kim
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.
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 F-1.

Some directions:

1. To reduce flow f_uv on edge (u,v) to f_uv-1 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?
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 Ford-Fulkerson
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
    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 12-08-2010 08:00 PM
Online version pages
07:45 PM ET (US)
Does anyone knows the reading page for chapter 8 of the on-line version text book?
Yoav FreundPerson was signed in when posted
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.
^     All messages            182-197 of 197  166-181 >>

Print | RSS Views: 6229 (Unique: 1077 ) / Subscribers: 13 | What's this?