Remarks: In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your algorithms. Prove that it works. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation. . Question 2: Given a graph G(V, E) a set I is an independent set if for every u,vEI, uv, uv E. A Matching is a collection of edges { so that no two edges in the matching share a common vertex. A verter cover is a collection U CV of vertices so 1. Show that the largest size matching in a graph is no larger than the size of an 2. Show that if I is an independent set then G(V - I) (namely, the graph with 3. Give an example for a graph so that the Maximum Matching is strictly smaller 4. A clique is a collection C of vertices U so that for every u, u C. uv E E. Say that for every edge uv E either u E U or v E U arbitrary vertex cover in the graph. vertices V - I, restricted to edge with both endpoints in V -I is) a Vertex Cover. than the minimum Vertex Cover that we are given an algorithm that finds a clique of maximum size in time f(n) Give an O(n2) f(n) time algorithm to find the maximum independent set and the minimum vertex cover in the graplh