1. Let T ≥ 1 be any integer. Prove that VCdim(L(Bd ,T )) ≥ 0.5T log(d).

Hint: Construct a set of T 2 k instances by taking the rows of the matrix A from the previous question, and the rows of the matrices 2A,3A,4A, . . ., T 2 A. Show that the resulting set is shattered by L(Bd ,T ).

2. Efficiently Calculating the Viola and Jones Features Using an Integral Image: Let A be a 24×24 matrix representing an image. The integral image of A, denoted by I (A), is the matrix B such that Bi , j =_ i _≤i , j _≤j Ai , j . _ Show that I (A) can be calculated from A in time linear in the size of A. _ Show how every Viola and Jones feature can be calculated from I (A) in a constant amount of time (that is, the runtime does not depend on the size of the rectangle defining the feature).