(15 points) Submodularity Q 1.1 (5 points) Prove that the coverage function from our lecture is a monotone submodular function. Recall that the coverage function takes a collection of sets {Si}n i=1 and outputs the size of their union |S1 S2 Sn|. Solution: Q 1.2 (5 points) Let f be a monotone submodular function. Show that for any two sets S and T: f(T)f(S) eT (f(S+ e)f(S)). Solution: Q 1.3 (5 points) Let f be a monotone submodular function. Show that the following function is also submodular: h(A) = min (f(A),f(V/A)) where V is the universal set of all elements