Question $4($k$-$means, $40/100)$ Using the same terminology adopted in our course, we shall

refer to the $$k$-$means$$ algorithm as the algorithm that initializes the centroids randomly,

followed by a $$refinement phase$$ where the clusters are improved further. We shall refer to

$$k$-$means$++$ as the algorithm that only selects the centroids, so as to provide some

theoretical guarantees. Consider the following points in the $2$D Euclidean space: p$1=(0,0),$

p$2=(0,1),$ p$3=(0,2),$ p$4=(2,0),$ p$5=(3,0),$ p$6=(4,1),$ p$7=(5,0),$ p$8=(7,0),$ p$9=(8,0),$ p$10=(8,1).$ Let

k$=3.$