1. Here is a randomized algorithm for MAX-CUT on an undirected graph G = (V,E): 1. Initialize S to be the empty set 2. For every vertex v in V: 3. Put v into S with probability 1/2 4. Let T = V\S be the complement of S 5. Output (S,T) Recall that E(S, T) CE is the set of edges that have one endpoint in S and the other endpoint in T, ie., E(S, T) = {(u, u) : x S, u E T). The size of the cut is | E(S, T)1. (a) Show that the above algorithm is a 1/2-approximation in expectation for MAX-CUT That is, the expected size of the output cut is at least half the size of a maximum cut. Hint: use linearity of expectation to show that in expectation, half of the edges in the entire graph are in E(S, T).) (b) Argue that, for any graph G-(V, E), there exists a cut of size at least E1/2. 1. Here is a randomized algorithm for MAX-CUT on an undirected graph G = (V,E): 1. Initialize S to be the empty set 2. For every vertex v in V: 3. Put v into S with probability 1/2 4. Let T = V\S be the complement of S 5. Output (S,T) Recall that E(S, T) CE is the set of edges that have one endpoint in S and the other endpoint in T, ie., E(S, T) = {(u, u) : x S, u E T). The size of the cut is | E(S, T)1. (a) Show that the above algorithm is a 1/2-approximation in expectation for MAX-CUT That is, the expected size of the output cut is at least half the size of a maximum cut. Hint: use linearity of expectation to show that in expectation, half of the edges in the entire graph are in E(S, T).) (b) Argue that, for any graph G-(V, E), there exists a cut of size at least E1/2