13.5.1. Finding Minimum Distance

Try these first

1. 1.

   Define the Closest Pair Problem.

   Hint

   Think about distance between two points.

2. 2.

   What is the time complexity of the brute force solution?

   Hint

   Consider all possible pairs.

3. 3.

   What is the time complexity of the divide-and-conquer approach to the Closest Pair Problem?

   • O(n)
   • O(n^2)
   • O(n log n)

   Hint

   Think about sorting and how it contributes to the complexity.

4. 4.

   Is the Closest Pair Problem solvable using a brute force approach?

   • True
   • False

   Hint

   Recall the definition and methods used.

5. 5.

   Suppose you have 100 random points scattered on a plane. Describe how you would implement the Divide and Conquer algorithm step by step.

   Hint

   Think about how you handle distances.

6. 6.

   Create a dataset of points and manually compute the closest pair using both brute force and divide and conquer methods. Compare the results.

   Hint

   Use graphing tools for visualization.