Consider the following learning problem: Let the domain be X = R, and let C = Cs be the class of concepts defined by unions of s intervals.

Consider the following learning problem: Let the domain be X = R, and let C = Cs be the class of concepts defined by unions of s intervals. That is, each concept c is defined by real numbers a1 ≤ b1 ≤ · · · ≤ as ≤ bs where c(x) = 1 if and only if x ∈ [a1, b1]∪ · · · ∪[as, bs].

Describe an efficient algorithm that learns the class Cs for every s, assuming that s is known ahead of time to the learner. You should describe a single algorithm that works for all Cs, provided that s is known so that the learner can choose the number of examples needed as a function of , δ and s. You can use any hypothesis space you wish. Prove that your algorithm is PAC (i.e., produces a hypothesis with error at most with probability at least 1 − δ), and derive an exact expression for the number of examples needed. Also argue briefly that your algorithm runs in time polynomial in 1/, 1/δ and s.