Problem 1 In this problem you'll play around with some of the concept classes we discussed in class (and some of their close friends). (i) Let S be a subset of {1,...,n}. The parity function corresponding to S is the Boolean function f:{0,1}" + {0,1}, f(x1, ... , wn) = xi mod 2 ies which counts whether the number of input bits in coordinates indexed by S is odd or even. True or false: For every SC [n], the parity function corresponding to S is computed by a poly(n)- term DNF. (Justify your answer.) (ii) A concept c: {0, 1}" + {0,1} is said to be monotone if whenever two inputs x, y E {0, 1}" satisfy x