3.26 Symmetric functions. A function h: f0; 1gn ! f0; 1g is symmetric if its value is uniquely determined by the number of 1's in the input. Let C denote the set of all symmetric functions.

(a) Determine the VC-dimension of C.

(b) Give lower and upper bounds on the sample complexity of any consistent PAC learning algorithm for C.

(c) Note that any hypothesis h 2 C can be represented by a vector (y0; y1; : : : ; yn)

2 f0; 1gn+1, where yi is the value of h on examples having precisely i 1's.

Devise a consistent learning algorithm for C based on this representation.