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 with 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 deterministie 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 most 2. 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 with 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 deterministie 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 most 2