Problem 4. (5 pts) k-means Clustering on the Line Before we describe the problem of k-means clustering, we give a definition and discuss some of its properties Definition: Given a set X of m real numbers, , ..., Im, we denote their cost as () (1 pts) Denote -1 z. Prove that for any real it holds that TEX TEX TEX and use this identity to infer that the point y on which the cost (X) is obtained is in fact - Le (i) (1 pts) Use the above fact to give a 0(1)-time algorithm that takes as input X, and (X) as defined above and in addition another new input point zm+1 and returns the new center {T +1} the new cost of the m + 1 points (X U {Tm+1)) and We can now discuss the problem of k-means clustering in one-dimension. Your input is composed ofn datapoints n and your goal is to partition the n real-value points into k clusters C1,., Ck as to minimize (G) (iii) (3 pts) Give a O(n2k)-time algorithm for computing the best k-means clustering cost for a given input composed of n real-value datapoints Hint: First prove that for any 3 distinct points in X: z