Exercise 6.14

• Step 2 of Lloyd’s Algorithm: According to exercise 6.13 (b), if we construct $S_j$ to be all points closest to ${\mu }_j$, we minimize $E_{\mathit{in}}$ with fixed ${\mu }_1,\dots ,{\mu }_k$, which won’t increase $E_{\mathit{in}}$.
• Step 3: From exercise 6.13(a), when we have fixed clusters of $S_1,\dots ,S_k$, if we choose each ${\mu }_j$ to be the centroid of $S_j$, we minimize $E_{\mathit{in}}$ with fixed clusters. The $E_{\mathit{in}}$ will not increase.

Also, there are only finite number of different partitions for the data points, So the Lloyd’s algorithm won’t run forever, it must eventually stop iterating.