(4) (20 points) In this problem, we want to show that properly PAC-learning monotone k-sparse disjunctions is NP-hard, by reducing from Set Cover. To this end, give a polynomial-time reduction from Set Cover to the following problem: Sparse Monotone Disjunction Input: labelled samples (x1,y1),,(xm,ym) where xi{0,1}r and yi{0,1} Goal: Find sparsest monotone disjunction h consistent with all labels, i.e. h(xi)=yi for 1im Sparsest means h involves as few literals as possible. In other words, your algorithm reads an input instance I of Set Cover and convert it to an input instance I of Sparse Monotone Disjunction, such that I has a small Set Cover if and only if I has a sparse monotone disjunction Justify why your reduction algorithm works. (Techniques from Notes11 can further reduce from Sparse Monotone Disjunction to the corresponding proper learning problem, but you are not required to show this latter step.)