(2) ( 30 points) We now show the VC dimension of linear threshold functions in n-dimensional Euclidean space is n+1, generalizing the result in Notes 05 . In the following, given a finite set S={s1,,sk} of points in Rn, the convex hull of S contains every convex combination of points in S, that is, the convex hull contains every point that can be written as 1ikisi such that i0 and 1iki=1. Let C be the concept class of linear threshold functions in Rn. (a) Prove that VCDim(C)n+1. In other words, find a set of n+1 points in Rn that is shattered by C. Prove that your set is shattered. (b) Show that VCDim(C)n+1 using Radon's Theorem, which says: Radon's Theroem: Any set S of n+2 points in Rn can be partitioned into two disjoint subsets S1 and S2 whose convex hulls intersect. (c) Prove Radon's Theorem. Hint: Useful fact from linear algebra: Any n+1 points x1,,xn+1 in Rn are linearly dependent, that is, there are real numbers 1,,n+1, not all zeros, such that 1x1+ +n+1xn+1=0. Hint: You may prove Radon's Theorem by first proving the following statement: Any n+2 points x1,,xn+2 in Rn are affinely dependent, that is, there are real numbers 1,,n+2, not all zeros, such that 1x1++n+2xn+2=0 and 1++n+2=0