1

edit
# Changes

→Closest Pair

One of the more common ~~algorithm ~~algorithms used to find the closest pair is the Brute-force algorithm; which is calculating the distances of all the ~~point ~~points ( O(n^2) notation):

n=total number of ~~pints~~points

n(n-1)/2

then simply look for the pair of points that has the smallest distance between each other. However, this algorithm was evident to be slow.

This is the function used in the closestPair.c program that Stephanie used for ~~here ~~her assignment 1:

double brute_force(point* pts, int max_n, point *a, point *b)

This the profile:

Flat profile:

Each sample counts as 0.01 seconds.

% cumulative self self total

time seconds seconds calls ms/call ms/call name

99.78 41.58 41.58 16384 2.54 2.54 brute_force

0.14 41.64 0.06 closest

0.05 41.66 0.02 cmp_x

0.02 41.67 0.01 cmp_y

As a consequence, we presume ~~“parallellazing” this algorithm ~~that by making the brute force function parallel using CUDA technology will speed up the process significantly.

Github link [https://github.com/sezar-gantous/GPU610-ClosestPair here]

=== Assignment 3 ===