GATE 2024 DA Q.42: solution and answer

Official answer: ASource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Single linkage merges the two clusters with the smallest minimum pairwise distance. The smallest entries in the table are $d(x_1,x_2)=1$ and $d(x_4,x_5)=1$.

2. Merge $\{x_1,x_2\}$ at height 1 and $\{x_4,x_5\}$ at height 1.

3. Recompute the cluster distances with the minimum over pairs: $d(\{x_1,x_2\},x_3)=\min (4,3)=3$, $d(\{x_1,x_2\},\{x_4,x_5\})=\min (3,6,5,3)=3$, $d(x_3,\{x_4,x_5\})=\min (2,5)=2$.

4. The smallest is 2, so $x_3$ joins $\{x_4,x_5\}$ at height 2, giving $\{x_3,x_4,x_5\}$.

5. Finally $d(\{x_1,x_2\},\{x_3,x_4,x_5\})=\min (4,3,3,5,6,3)$ over all cross pairs $=3$, so the two groups merge at height 3.

6. The tree is $((x_1,x_2),(x_3,(x_4,x_5)))$: a pair $x_1,x_2$, a pair $x_4,x_5$ with $x_3$ joining it, and the two groups joined at the top. This is option A.

7. Option B has $x_3$ joining $\{x_1,x_2\}$ while $x_4,x_5$ stay a separate pair, but $x_3$ is closer to $\{x_4,x_5\}$ (distance 2) than to $\{x_1,x_2\}$ (distance 3). Option C pairs $x_3$ with $x_4$ and then adds $x_5$, but $x_4$ and $x_5$ (distance 1) merge before $x_3$ can join either. Option D merges $x_3,x_4$ as a pair and leaves $x_5$ until last, but $x_5$ is closest to $x_4$ (distance 1).