Consider the following problem. The input is a graph G (V,E). Feasible solutions are subsets S of the vertices V. The objective is to maximize the number of edges witlh one endpoint in S and one endpoint in V -S (a) Give a simple polynomial-time randomized algorithm for this problem and show that it is 2 approximate. Hint: Flip a coin for vertex and consider analysis for MAX2SAT from class. (b) Develop a deterministic polynomial-time 2-approximation algorithm for this prob lem using the method of conditional expectations, which considers the vertices one by one, but instead of flipping a coin for each vertex v, puts v in the bipartition that would maximize the expected number of edges in the cut if coin flips were used for the remaining vertices. (c) Give a simple greedy algorithm that ends up implementing this policy. (d) Prove that this greedy algorithm has approximation ratio at most2 Consider the following problem. The input is a graph G (V,E). Feasible solutions are subsets S of the vertices V. The objective is to maximize the number of edges witlh one endpoint in S and one endpoint in V -S (a) Give a simple polynomial-time randomized algorithm for this problem and show that it is 2 approximate. Hint: Flip a coin for vertex and consider analysis for MAX2SAT from class. (b) Develop a deterministic polynomial-time 2-approximation algorithm for this prob lem using the method of conditional expectations, which considers the vertices one by one, but instead of flipping a coin for each vertex v, puts v in the bipartition that would maximize the expected number of edges in the cut if coin flips were used for the remaining vertices. (c) Give a simple greedy algorithm that ends up implementing this policy. (d) Prove that this greedy algorithm has approximation ratio at most2