# Learning From Data – A Short Course: Exercise 5.1

Consider hypothesis sets and that contain Boolean functions on 10 Boolean variables, so . contains all Boolean functions which evaluate to +1 on exactly one input point, and to elsewhere; contains all Boolean functions which evaluate to +1 on exactly 100 input points, and to -1 elsewhere.

(a) How big (number of hypotheses) are and ?

(b) How many bits are needed to specify one of the hypotheses in ?

(c) How many bits are needed to specify one of the hypotheses in ?

(a) Each input point has 10 Boolean features, so: ,

(b) 10.

(c) .

Isn’t |H_100| = 2^10 choose 100? 2^1000 seems extremely high since there’s only 2^1024 possible functions.

Thank you. I updated the answer. I think the answer should be the combination without repetition with n be 2^10 and r be 100 (https://www.mathsisfun.com/combinatorics/combinations-permutations.html).