Exercise $2.$ In class, we stated that some decision tree algorithms only provide binary splits. If

such an algorithm creates a binary split based on a nominal attribute with $k$ distinct values, say,

$\{v_1,v_2,$dots,$v_k\},$ it must consider $2^{k-1}-1$ different partitions. Can you prove this statement for

every $k>1?$

Hint: Use mathematical induction

Exercise $3.$ Consider, again, the table for problem $1.$ Use the CHAID algorithm create a decision

tree of height $1,$ that is$,$ one root and multiple children.