Algorithms for Data Science End Term: 31 August 2025 (May 2025 term)

Consider a sample of 5 data-points for a classification problem with 3 classes. We can have at most k different labellings of these 5 points. What is the tightest upper bound for k?

For a binary classification setup with a single feature in $\mathbb{R}$ and labels in $\{0, 1\}$, consider this hypothesis class:

$\mathcal{H} = \{h_{a_1 \ldots a_6} : a_1 < a_2 < a_3 < a_4 < a_5 < a_6, \quad a_i \in \mathbb{R}\}$

where $h_{a_1 \ldots a_6}$ is defined as:

$h_{a_1 \ldots a_6}(x) = \begin{cases} 1, & x \in [a_1, a_2] \cup [a_3, a_4] \cup [a_5, a_6] \\ 0, & \text{otherwise} \end{cases}$

Find the VC dimension of $\mathcal{H}$.