In the maximum cut problem, you are given an undirected graph G = (V, E) with a weight w(e) on each edge, and you wish to separate the vertices into two sets S and V S so that the total weight of the edges between the two sets is as large as possible. For each SC V define w(S) to be the sum of all w(e) over all edges {u, v} such that Sn{u, v}|= 1. Obviously, the maximum cut is about maximizing w(S) over all subsets of V. Consider the following local search algorithm for the maximum cut problem: Algorithm 1 procedure MAX CUT(G) start with any SCV while there is a subset S' CV such that ||S'|-|S|| = 1 and w(S')> w(S) do set S = S' end while end procedure (a) Show that this is an approximation algorithm for the maximum cut problem with ratio 2. (b) is it a polynomial-time algorithm?