2nd question from Algorithm , design of algorithm

This question can be attempted in groups. A fundamental problem in machine learning and data analytics is to partition or classify objects in a 'natural way based on their distances to each other. In this question, you are given an integer N, and n points x1,x2,...,xn in a horizontal line. We want to partition the n points into N groups so that intuitively within each group the points are 'close together. The following is an example of what may be a good way of partitioning the following n = 8 points into N = 3 groups, and what may be a bad way: 1 2 3 6 8 12 13 15 Good? Bad? More precisely, each point Xi is a number on the x-axis. To measure how 'good' a partitioning is, we define the error of a group of points Xp, Xp+1,...,xq to be (Ep - M)2 + (p+1 -H)+ ... + (xq u)? where h = (xp + Xp+1+...+Xq)/(q- p+1) is the average of the points. Our objective is to find the optimal way of partitioning the points into N groups so that the sum of errors of all groups is minimised. For example, the 'bad' way of partitioning for the above example gives an error of: Group 1: average = (1+2)/2 = 1.5, error = (1 - 1.5)2 + (2 - 1.5)2 = 0.5. Group 2: average = (3+6+8+12)/4 = 7.25, error = (3 - 7.25)2 + (6 - 7.25)2 + (8 7.25)2 + (12 7.25)2 = 42.75. Group 3: average = (13+15)/2 = 14, error = (13 - 14)2 + (15 14)2 = 2. Total error = 0.5 + 42.75 + 2 = 45.25. We divide the points in such a way that only consecutive points (along the line) may fall into the same group. (a) Design an efficient algorithm for this problem. You should: (the following is described in terms of the design of a dynamic programming algorithm, since you almost certainly should use it) In plain English or using some mathematical notation, give a recursive formulation of the problem. (Hint: one possible approach is to define F(i,k) to be the error of the optimal partition of the first i points 21,..., & into k groups, where i