Question $1$: Consider the Differentiated Set Coverage Problem:

Input: n items, U $=1,2,...,$ n$,$ coverage requirements of the items f $=$f$1,$ f$2,...,$ fn$,$

m sets, S$1,$ S$2,...,$ Sm$,$ price of the sets p $=$p$1,$ p$2,...,$ pm$.$

Let x $=$x$1,$ x$2,...,$ xm$$ be the selection decisions of the sets, xi in $\{0,1\}.$

Output: A minimum price selection x of the sets S$1,$ S$2,...,$ Sm that can cover the items in

U at least f times.

Ex: Let n $=5$ and U $=1,2,3,4,5$ having coverage requirements f $=1,2,1,2,1.$

Let m $=5$ and S$1=\{1,2\},$ S$2=\{2,3,4\},$ S$3=\{2,5\},$ S$4=\{3,4\},$ S$5=\{1,4\}$ with

prices p $=5,6,10,2,4.$

For instance, item j $=2$ in U should be covered by at least f$2=2$ different sets Si

$.$ We

note that item $2$ can be covered by S$1$ with price p$1=5,$ by S$2$ with price p$2=6$ and by S$3$

with price p$3=10.$

$1.$ Determine a greedy selection rule for the sets. Design a greedy algorithm for the

Differentiated Set Coverage Problem and report the pseudocode.

$2.$ Discuss the time complexity of your greedy algorithm. Is it efficient? Can your

algorithm find the optimum solution?

$3.$ Implement your algorithm in Python. Use the input given in the example and report

the console outputs and your Python code scripts.