2. (20 pts extra credit) Even though in this class we focus on those greedy algorithms that generate optimal solutions, in general a greedy algorithm may not give an optimal solution. So, we are interested in those greedy algorithms that generate a good enough solution, i.e., not too far from the optimal solution. Let us consider one such problem as follows Given subsets Si, S2, . Sn of a set S of points and an integer m, a maximum m-cover is a collection of m of the subsets that covers the maximum number of points of S. Finding a maximum m-cover is a computationally hard problem. Give a greed;y algorithm that achieves approximation ratio 1-1/e; i.e., let y be the maximum number of points that can be covered by m subsets and r be the number of points that are covered by the m subsets generated by your algorithm, then give a greedy algorithm such that x 2 (1 - 1/e )y Some useful hints: You may want to use the inequality (1-1/m)rn 1/e for integer m > 1. . You may want to use induction at some point. 2. (20 pts extra credit) Even though in this class we focus on those greedy algorithms that generate optimal solutions, in general a greedy algorithm may not give an optimal solution. So, we are interested in those greedy algorithms that generate a good enough solution, i.e., not too far from the optimal solution. Let us consider one such problem as follows Given subsets Si, S2, . Sn of a set S of points and an integer m, a maximum m-cover is a collection of m of the subsets that covers the maximum number of points of S. Finding a maximum m-cover is a computationally hard problem. Give a greed;y algorithm that achieves approximation ratio 1-1/e; i.e., let y be the maximum number of points that can be covered by m subsets and r be the number of points that are covered by the m subsets generated by your algorithm, then give a greedy algorithm such that x 2 (1 - 1/e )y Some useful hints: You may want to use the inequality (1-1/m)rn 1/e for integer m > 1. . You may want to use induction at some point