he set cover problem is the following:

Input: U $=\{1,...,$ m$\}$ and S a set of n subsets of U such that $$

s in S s $=$ U $($the

union of the subsets in S is U $).$

Output: A set T $=\{$s$1,...,$ sk$\}$ S of minimum size $($i$.$e$.$ minimum k$)$ such that$$

s in T s $=$ U $.$

We will look at two greedy algorithms that attempt to solve the set cover problem.

$$ At each step, pick the set s in S $\backslash$ T $($i$.$e$.$ a set that has not been chosen yet$)$

of largest size to add to T $,$ breaking ties arbitrarily. Stopping when the union

of the sets in T is U $.$

$$ At each step i$,$ maintain Ti $=\{$s$1,...,$ si$\}$ and Ci $=$

s in Ti s$.$ Pick si$+1$ as the

set in S $\backslash$ Ti that contains the maximum number of uncovered $($i$.$e$.$ U $\backslash$ Ci$)$

elements, breaking ties arbitrarily. Update Ti$+1,$ Ci$+1$ as appropriate. Stopping

when Ci $=$ U $,$ for some i$.$

As set cover is a NP$-$Hard problem, the above algorithms are incorrect since they

take polynomial time. Therefore, for each of the algorithms, give a counterexample

to show that the algorithm is incorrect. Give the input, the steps the algorithm

will take to obtain its output, and why this output is not optimal by providing a

better solution.

$2$