1. Suppose that a list contains the values 20 44 48 55 62 66 74 88 93 99 at index positions 0 through 9. Trace the values of the variables….

## Prove that for r = 2 it holds that VCdim(H1 ∪H2) ≤ 2d +1.

1. (*) Prove that for *r *= 2 it holds that VCdim*(**H*1 ∪*H*2*) *≤ 2*d *+1.

2. Dudley classes: In this question we discuss an algebraic framework for defining concept classes over R*n *and show a connection between the VC dimension of such classes and their algebraic properties. Given a function *f *: R*n *→R we define the corresponding function, *POS*( *f *)(*x*) = 1[ *f *(*x*)*>*0]. For a class *F *of real valued functions we define a corresponding class of functions *POS*(*F*) = {*POS*( *f *) : *f *∈ *F*}. We say that a family, *F*, of real valued functions is *linearly closed *if for all *f **, **g *∈ *F *and *r *∈R, ( *f *+*rg*)∈*F *(where addition and scalarmultiplication of functions are defined point wise, namely, for all *x *∈ R*n*, ( *f *+*rg*)(*x*)= *f *(*x*)+*rg*(*x*)). Note that if a family of functions is linearly closed then we can view it as a vector space over the reals. For a function *g *: R*n *→R and a family of functions *F*, let *F *+ *g *d=ef { *f *+ *g *: *f *∈ *F*}. Hypothesis classes that have a representation as *POS*(*F *+ *g*) for some vector space

of functions *F *and some function *g *are called *Dudley classes*.