deletions | additions       diff --git a/q3.tex b/q3.tex  index d70d345..48e4fb4 100644  --- a/q3.tex  +++ b/q3.tex 
...
$2c(B) = 2\sum\nolimits_{u \in B, v \in A, (u,v) \in E}w_{u,v} >=\sum\nolimits_{e \in E}w_e >= OPT $  \textbf{3.}  For the greedy algorithm, start off with both sets A and B empty. Then pick a random vertex and place it in set A. Then pick the next vertex and put it in B so that it will maximize the number of edges between A and B. After this, choose and vertex that will maximize the number of edges between the two sets and place it in the set that maximizes the number of edges. Continue this operation until you run out of vertices.  This is a polynomial time algorithm. There are a total number of $n$ iterations, one for each time you pick a vertex. Then to pick a vertex you must look at every single edge and worst case there will be $n^2$ number of edges. So that means in total there should be $n^3$ operations, which is polynomial.   This is a 2-approximation algorithm. Let the total number of edges in the graph be $E$. Let $n$ be the number of nodes. For every single edge in the graph, it has two nodes. Let's label the first node as the $Start$ node and the other node at the $End$ node.   When the $End$ node gets added to the graph problem, the edge is created. Now let $e_i$ be the number of edges that the node $i$, is considered the $End$ node. Since every single edge has one $End$ node, that means $\sum{i=1}{n} e_i = E$the sum from i=1 to n of ei=E (which is the total number of edges)