Task $3(50$ marks$)$

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_1,x_{2,\text{d}\text{o}\text{t}\text{s}},x_n$ 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:

More precisely, each point $x_i$ is a number on the x$-$axis. To measure how 'good' a

partitioning is$,$ we define the error of a group of points $x_p,x_{p+1},$dots,$x_q$ to be

$(x_p-{)}^2+(x_{p+1}-{)}^2+$cdots$+(x_q-{)}^2$

where $=\frac{x_p,x_{p+1},\text{d}\text{o}\text{t}\text{s}\text{,}{x}_q}{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.

For example, the 'bad' way of partitioning for the above example gives an error of:

Group $1$: average $=\frac{1+2}{2}=1\mathrm{.}5,$ error $=(1-1\mathrm{.}5{)}^2+(2-1\mathrm{.}5{)}^2=0\mathrm{.}5$

Group $2$: average $=\frac{3+6+8+12}{4}=7\mathrm{.}25,$

error $=(3-7\mathrm{.}25{)}^2+(6-7\mathrm{.}25{)}^2+(8-7\mathrm{.}25{)}^2+(12-7\mathrm{.}25{)}^2=42\mathrm{.}75$

Group $3$: average $=\frac{13+15}{2}=14,$ error $=(13-14{)}^2+(15-14{)}^2=2$

Total error $=0\mathrm{.}5+42\mathrm{.}75+2=45\mathrm{.}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_1,$dots,$x_i$ into $k$

groups, where $in$ and $kN.$ 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$).$