1
edit
Changes
→Closest Pair
The closest pair problem can be explained simply by imagining a random set of points spread in a [http://en.wikipedia.org/wiki/Metric_space metric space]. Now the process of finding two points with the smallest distance between them is called the closest pair problem.
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 pintspoints
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 is 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
System specifications:
OS: Ubuntu 12.04 32-bit
CPU: Intel(R) Core 2 Duo(R) CPU E4600 @ 2.40GHz x 2
RAM: 2GB DDR2
GPU: nVIDIA GEFORCE GT 620
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 ===
