13.6.2. Setting Up S_y

Try these first

1. 1.

   Define the closest pair problem.

   Hint

   Think about real-world applications.

2. 2.

   What is the naive approach to solving the closest pair problem?

   Hint

   Consider how many pairs there are.

3. 3.

   What is the time complexity of the naive closest pair algorithm?

   • O(n log n)
   • O(n)
   • O(n²)

   Hint

   Consider the number of pairs formed with n points.

4. 4.

   True or False: The divide and conquer method reduces the time complexity of the closest pair problem.

   • True
   • False

   Hint

   Think about efficiency gains.

5. 5.

   Given a set of 10 random (x, y) coordinates, implement the divide and conquer algorithm to find the closest pair. Explain each step you took in solving the problem.

   Hint

   Think of how sorting aids in your recursive splits.

6. 6.

   Design a scenario where the naive closest pair algorithm could significantly lag behind the divide and conquer method, quantifying the difference in time taken for n=1000 points.

   Hint

   Compare computational efforts of both approaches in practical terms.