Consider the hypothesis class of all conjunctions of literals over d vari- ables. The empty conjunction ho is interpreted as the all-positive hy- pothesis (ho(x) = 1 for all x). Any conjunction which contains a vari- able and its negation (like ,, etc.) is interpreted as the all-negative hypothesis. We assume realizability, which in this context, means that there exists a Boolean conjunction that generates the labels. Thus, each example (x, y) = x x y consists of an assignment to the d Boolean variables and its truth value. For example, for d = 3 and the true hypothesis f(x) = 72, the training set S may contain ((1, 1, 1), 0), ((1, 0, 1), 1), ((0, 1, 0), 0), ((1, 0, 0), 1). (a) Prove that [H] = 3 + 1. (b) Prove that the hypothesis class of all conjunctions over d variable is PAC learnable and bound its sample complexity m(e, 6). (c) Design an algorithm (using pseudocode) that implements the ERM rule and whose time is polynomial in dm.