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,pj) = p(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
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
What is the time efficiency for your recursion algorithm? (set up equation and solve)
Grading Rubric Can find on Canvas
