3) (20 points) Consider PAC learning s-sparse disjunctions. The end of Notes09 outlines the "Further Improved Algorithm" that finds a disjunction h(x) consistent with all negative samples and 1/2 fraction of positive samples, using Greedy Heuristic for Set Cover. (a) Argue that h(x) involves at most sln(2/) literals. (b) State and prove a variant of Theorem 2.1 of Notes09 and apply your theorem to show the following: Let c be any s-sparse disjunction. Given O(e1(ln1+sln1lnn)) independent samples drawn from EX (c,D), with probability 1, Further Improved Algorithm outputs a hypothesis h(x) with error . (The key part is to justify why O(c1(ln1+slnc1lnn)) samples suffice.)