Consider a learning problem where the examples are described by n boolean attributes and the target concept is a conjunction of k of the n (unnegated) attributes. an algorithm to find the target concept is as follows: the initial hypothesis is the conjunction of all n attributes. for each misclassified positive example, discard any attributes from the hypothesis which are false in the positive example. suppose the examples for this learning problem are drawn from the uniform distribution, so every combination of attribute values has equal probability of appearing. further, the attributes are all independent of one another, and there is no noise. derive a formula that bounds the number of examples the algorithm needs to see to guarantee that it will find the target with probability exceeding α, in terms of α, k and n.