(Part a not required as b is separate)

b) For the class H of axis-aligned n-dimensional rectangles in R, that is H = {[ai, b] x [an, bm] : i, b R} (1) Give a PAC-learning algorithm. (2) Prove that your algorithm satisfies the conditions for PAC learnability. (3) How does the sample complexity vary as a function of n? (4) Your answer should not exceed 2 pages