(i) Show that the VC dimension of C is 0(log N). (ii) Show that the VC dimension of C is (2(log N/ log log N). (Hint: The fact that the product of all prime numbers up to k is 290\") may be useful, and also the Prime Number Theorem.) Problem 4 (You may assume the results of problem 3 for this problem even if you did not solve problem 3.) Taking N > 00, part (ii) of problem 3 implies that there is no a prion" xed sample size which sufces for PAC learning the concept class C of all arithmetic progressions over the innite domain N for all distributions. To be more precise, it tells us that there is no function m(1/5,1/6) such that the following holds: There is an algorithm which, given 5, 6 and access to EX ((3, 'D) where D is any distribution over N and c is any arithmetic progression over N, draws m(1/e, 1/6) samples from EX (c, D) and with probability 1 6 outputs an Eaccurate hypothesis for c. However, while there is no xed sample size m(1/5, 1/6) that sufces for every distribution, in fact for every distribution there is some sample size that suffices. Establishing this is the point of the current problem. Show that the following holds: For every distribution D over N, there is a function mp(1/e, 1/6) (which may depend on D) and an algorithm AD (which also may depend on D) such that the following holds: If AD is given 5,6 and access to EX (0, D) where c is any arithmetic progression Over N, it draws mp(1/e, 1/6) samples from EX (c, D) and with probability 1 6 outputs an 5 accurate hypothesis for c