For a given a graph G = (V,E), a vertex cover of G is a subset of vertices C V such that each edge of G has at least one endpoint in C. The goal of the vertex cover problem is to find the optimal vertex cover C with the minimum number of vertices. Consider the following randomized algorithm for vertex cover. Step 1: Start with C = . Step 2: Pick an edge e uniformly at random from the edges that are not covered by C (i.e., if e has endpoints u and v, then {u, v} \ C = . and add a random endpoint of e to C. Step 3: If C is a vertex cover, terminate and output C; else go to Step 2. Answer the following questions: (a) Consider the very first iteration of the algorithm. What is the probability that a vertex from the smallest vertex cover C is added to C? (Hint: for each edge e 2 E, at least one endpoint of e must be in C.) (b) Consider the second iteration of the algorithm. What is the probability that a vertex from the smallest vertex cover C is added to C? (Hint: you should discuss the two scenarios of whether a vertex from C is added to C in the first iteration or not.) (c) Let k be the number of vertices in the smallest vertex cover C. Show that the expectation of the number of vertices of C is 2