Exercise 5.1

(a) For $X={\{-1,+1\}}^{10}$, there are $2^{10}$ possible input points in total. Given the number of input points $N$, there are $\left(\genfrac{}{}{0ex}{}{N}{1}\right)$ ways to select one of the input points to evaluate to $+1$, and the rest of the input points to evaluate to $-1$. There are $2^{2^{10}-N}$ ways to assign either $+1$ or $-1$ to the points not in the input data set. So there are total $\left(\genfrac{}{}{0ex}{}{N}{1}\right)2^{2^{10}-N}$ hypothesis functions in $H_1$. Similarly there are $\left(\genfrac{}{}{0ex}{}{N}{100}\right)2^{2^{10}-N}$ hypothesis functions in $H_{10}$.

(b)-(c) For both $H_1$ and $H_{10}$, we need $2^{10}$ bits to specify one hypothesis function. The $2^{10}$ bits can represent all the data points in the $X$ domain. If a bit position is 1, it indicates that the hypothesis function evaluates to $+1$ on the corresponding point, otherwise it evaluates to $-1$.

From above, we learned that the family of $H_{10}$ is more complex than the family of $H_1$, But their object complexity is the same.