deletions | additions       diff --git a/q3.tex b/q3.tex  index e6b2c03..9fdeca6 100644  --- a/q3.tex  +++ b/q3.tex 
...
So the number of edges that cross A and B = sum of the number of edges added by the $End$ nodes...  Which is $>=\sum\limits_{i=1}^n replace_contentgt;=\sum\limits_{i=1}^n  \frac{e_i}{2} = E$ (since this is how much the greedy algorithm adds each time)... Which is $>= replace_contentgt;=  \frac{E}{2}$ (since the sum of the $e_i$’s equal the total number of edges). So the number of edges that cross A and B from the greedy algo is $>= replace_contentgt;=  \frac{E}{2}$ Since the optimal value can only be $E$ at best that means this greedy algorithm is at most 2 times worse than the optimal solution. \textbf{4.}  Randomized algorithm: Just randomly place vertices in the two sets. This is obvious polynomial because there are no computations necessary.  This is a 2-time approximation algorithm. There are a total of E edges which is the max value the optimal solution can take. We need to show that this algo will on average give us $\frac{E}{2}$ cost. So let us number the edges from 1 to E. Let $e_i=1$ if that edge crosses from A to B and let it equal $0$ if it doesn't.  Now, $P(e_i=1)=$ the probability that the two nodes get placed into two different sets.  We take two random nodes and enumerate all their possibilities.  Node1-A, Node2-A  Node1-A, Node2-B  Node1-B, Node2-A  Node1-B, Node2-B  This shows us that for half the time, the edge will exist and for the other half it wont.   So the expected value of $e_i= P(e_i=1)*1=\frac{1}{2}$  So the expected value of all the $e_i$’s $=\frac{1}[2}*E$  So using this algorithm, the expected number of edges that should cross from A to B is $\frac{E}{2}$.  So using this algo the expected number of edges that should cross from A to B is $\frac{E}{2}$.  So this is a 2-time approximation algorithm.