Problem $5(3$ points$)$

The MIN SET COVER problem can be solved using the greedy approximation algorithm described in the textbook $($section $35\mathrm{.}3)$ and in the slides. Apply this algorithm to the following instance of MIN SET COVER:

$1.$ 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 the case of more than one choice, make either choice.

$2.$ Find any optimal solution to this instance.