Some comments and clarifications on Homework #3:

For problem 1;

Parts (i), (ii), (iii): Here I am not asking for an
new algorithm. Just briefly say repeat the algorithm for this
problem as described in class (or in our class notes), and 
briefly explain why it  has these 3 properties. 

Part (v), Hint: In a probabilistic algorithm you are allowed to choose a 
number at random from any given finite set . 
So if you choose a number uniformly at random from the set {3}, then you will
choosing 3 with probability = 1. So now you can do this more than once, essentially 
essentially not using any randomness, and picking which numbers you want to use. 

If you choose enough numbers  even deterministically (without any randomness). 
You can use them to get the right answer to the polynomial identity with probability = 1.


For Problem 3: The first sentence here should have been left. It was just a suggestion,
and ended up confusing some people. 

All you need to do here is answer the question: For which of the 4 graphs G is the probability of  
finding the min-cut of G exactly 1/2? And then explain why this is so.


For Problem 4: Hint: Consider what happens when you have a graph G with a unique min-cut
of size 1. 

Think of G as having one edge u----v  which divides G's vertices into a cut C=(L,R) 
where L = {v, and all vertices in G "to the left of u"} and 
R = {v and all vertices in G "to the right of v"}. 

Now notice what happens when this modified min-cut contraction algorithm
chooses to contract 1 vertex from L and one from R, noting that the edge 
between them cannot exist in G, (and so the resulting cut is not the min-cut).

And consider what the error probability of the algorithm is for G's which have
larger and larger L and R sets.