Exercise 4 (2 pts). The MIN SET COVER problem can be solved using the greedy approx imation algorithm described in the textbook (section 35.3) and in the slides. Apply this algorithm to the instance in Figure 3 1. Find any optimal solution to this instance 2. Give a trace of the algorithm on this instance. Note that the algorithm does not specify exactly how to break a tie when the numbers of uncovered elements are equal. In this case, you can select an arbitrary subset 3. Give any other trace (if a difserent trace exists) Ground set U={1,2, 3, . . . , 12} Family of subsets S, = {1,3.5, 7, 9, 11); (2, 4, 6, 8, 10, 12); S3 ,2,3,4; S4 5,6,7,8,9,10); Ss= {11, 12) Exercise 4 (2 pts). The MIN SET COVER problem can be solved using the greedy approx imation algorithm described in the textbook (section 35.3) and in the slides. Apply this algorithm to the instance in Figure 3 1. Find any optimal solution to this instance 2. Give a trace of the algorithm on this instance. Note that the algorithm does not specify exactly how to break a tie when the numbers of uncovered elements are equal. In this case, you can select an arbitrary subset 3. Give any other trace (if a difserent trace exists) Ground set U={1,2, 3, . . . , 12} Family of subsets S, = {1,3.5, 7, 9, 11); (2, 4, 6, 8, 10, 12); S3 ,2,3,4; S4 5,6,7,8,9,10); Ss= {11, 12)