Description
Implement a divide and conquer (recursive) and brute force (non-recursive) algorithm in
Python for calculating the Closest-Pair Problem. This problem calls for finding the two
closest points in a set of n points.
You can assume all points are represented by (x, y) Cartesian coordinates and the distance
between two points pi(xi
, yi) and pj (xj
, yj ) is the standard Euclidean distance d(pi
p
, pj ) =
(xi − xj )
2 + (yi − yj )
2
.
Here are the steps to complete the project:
• Step 1. Write the brute force algorithms in Python. The brute force algorithm checks
every combination using the above calculation.
• Step 2. Write the recursive algorithm. The recursive algorithm pseudo code is in
Figure 1 below.
• Step 3. Write functions to time the execution of each of the algorithms by creating
two additional functions:
effRec(n)
Start the clock
Call your recursive function
Stop the clock
Print the two closest points and time to calculate
effBF(n)
Start the clock
Call your brute force function
Stop the clock
Print the two closest points and time to calculate
2 CS2223 Project 2
Figure 1: Recursive Closest Pair Pseudo Code
• Step 3. Conduct a thorough experiment to compare the time efficiency of your recursive and non-recursive algorithms. Test at least 3 sets of points and provide the point
sets in your readme file.
Include the following point set to test your code:
[(0, 0),(7, 6),(2, 20),(12, 5),(16, 16),(5, 8),(19, 7),(14, 22),(8, 19),(7, 29),(10, 11),(1, 13)]
• Step 4. Write your professional report. Answer the following questions:
What is the time efficiency for your brute force algorithm? (set up equation and solve)
3 CS2223 Project 2
What is the time efficiency for your recursion algorithm? (set up equation and solve)
Grading Rubric Can find on Canvas
