Consider the instance space consisting of integer points in the x, y plane, where 0 ≤ x, y ≤ 10, and the set of hypotheses consisting of rectangles (i.e. being of the form (a ≤ x ≤ b, c ≤ y ≤ d), where 0 ≤ a, b, c, d ≤ 10).
What is the smallest number of training examples one needs to provide so that the Find-S algorithm perfectly learns a particular target concept (e.g. (2 ≤ x ≤ 4, 6 ≤ y ≤ 9))? When can we say that the target concept is exactly learned in the case of the Find-S algorithm, and what is the optimal query strategy?
I'd also like to know the answer w.r.t Candidate Elimination.
Thanks in advance.