Consider the following variant of the Halving algorithm for learning a concept from class C (suppose |C| is a power of 2). Upon receiving the next example, flip a (6-sided) fair dice. If the outcome is 1, 2, 3, or 4 return the outcome by the majority of functions in the version space (as in the regular Halving algorithm), and if the outcome is 5, or 6, return `+'. After the true label is revealed, update the version space as before. What is the tightest upper bound for the expected number of mistakes by this algorithm for adversarial inputs? a. 4(log2 |C|)/3 b. 3(log2 |C|)/2 C. d. e. None of the other answers are correct. log2 |C| 3 log2 |C| f. 2 log2 |C| g. The expected number of mistakes cannot be bounded by a function of |C|.

Consider the following variant of the Halving algorithm for learning a concept from class C (suppose |C| is a power of 2). Upon receiving the next example, flip a (6-sided) fair dice. If the outcome is 1, 2, 3, or 4 return the outcome by the majority of functions in the version space (as in the regular Halving algorithm), and if the outcome is 5, or 6, return `+'. After the true label is revealed, update the version space as before. What is the tightest upper bound for the expected number of mistakes by this algorithm for adversarial inputs? a. 4(log2 |C|)/3 b. 3(log2 |C|)/2 C. d. e. None of the other answers are correct. log2 |C| 3 log2 |C| f. 2 log2 |C| g. The expected number of mistakes cannot be bounded by a function of |C|.