## #1 K-means Clustering

Write an implementation of
k-means clustering algorithm using
Intel Threading Building Blocks technology. The algorithm gets input points in a plane (R
^{2}), the number of clusters
`K`

, and the number of iterations. It returns coordinates of the cluster centroids, and the assignment of the points
after the last iteration.

The algorithm works as follows. As an initialization, the first
`K`

points are taken as the initial set of cluster centroids. After that, the algorithm performs prescribed number
of iteration, whilst each iteration consists of the following steps:

- Each point is assigned to its neares cluster -- i.e., the cluster which has its centroid nearest by the Euclidean metrics. In case there are multiple clusters with centroids that are equidistant from the point being assigned, the cluster with the lowest index is considered the closest one.
- A new centroid is computed for each cluster. The centroid is in fact an average of all assigned points (computed per dimension). The task expects that integer arithmetics is used (i.e., all operations including the division is computed on integers). In case that a cluster has no points assigned to it (and thus computing new centroid will result in zero division error), the centroid should be preserved (no new centroid shall be computed).

The number of points are divisible by 1,024 and the number of clusters
`K`

will not exceed 256 (clusters are indexed from 0). All points will fit in RAM and the sum of all point coordinates
in one dimension as well as the sum of squares of coordinate diferences (Euclidean distance) will fit into signed 64-bit
integer.

Your solution must use a framework, which is available for you at
**
/mnt/home/_teaching/para/01-kmeans
**
(including the testing data, data generator, and serial implementation). Your solution is expected to modify only the

**file of the framework while you have to preserve the name of the implementation class (**

`implementation.hpp`

**) and it must implement the interface**

`KMeans`

**. The modified file**

`IKMeans`

**is also the only file you are expect to submit into your**

`implementation.hpp`

**directory. If you need to create additional headers (**

`submit_box`

**), add them to you submit box as well, but do not create any subdirectories.**

`*.hpp`

Use the attached Makefiles for compilation. When debugging, the
**
KMeans
** class has a bool template parameter

**. When the program is called with**

`DEBUG`

`-debug`

argument, the debugging version of the class is used. You may use it to print out debugging information,
but make sure that the regular (non-debug) version is not printing anything to the stdout.
Your solution will be tested on different datasets than you are provided. However, the evaluation data will be of the same size. The small partition (w2xx workers) will be used to measure the speedup.