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 x, X2X 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: 12 13 Good! H More precisely, each point x 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,...,xqto be (xp-H)+ (Xp+1-H) ++ (x - ) where = (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 minimized. Bad? 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-1.5) = 0.5 Group 2: average = (3+6+8+12) /4 = 7.25, error = (3-7.25) + (6-7.25) + (8-7.25)+(12-7.25) = 42.75 Group 3: average = (13+15)/2 = 14, error = (13-14) + (15 14) = 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. 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 x, ..., X into k groups, where in and k N. The value of F(i, k) can be found recursively: consider all possible locations where the last (k-th) group can begin.) Write a program in C++ of the algorithm that is based on this formulation (Pseudocode may be accepted however some points will be lost).