Question 5. (20 points) Divide-and-Conquer: Recall that we have discussed designing the algorithm to find the maximum subarray using DC strategy, the worst-case running time can be represented by a recurrence relation: T(n)=2T(n/2)+ e(n). For the closest pair problem (S is a set of n points on a line (1-dimensional, unsorted), find the shortest distance of two points among these n points, e.g., input: S = [1, 5, 8, 2, 15], output: d 1), the recursion-based algorithm (divide-and-conquer) can be used to find the solution, the basic idea behind the algorithm design is: 1. Divide the set S of n points by some point mid ES into two sets S, and S such that p

Question 5. (20 points) Divide-and-Conquer: Recall that we have discussed designing the algorithm to find the maximum subarray using DC strategy, the worst-case running time can be represented by a recurrence relation: T(n)=2T(n/2)+ (n). For the closest pair problem ( S is a set of n points on a line (1-dimensional, unsorted), find the shortest distance of two points among these n points, e.g., input: S=[1,5,8,2,15], output: d =1 ), the recursion-based algorithm (divide-and-conquer) can be used to find the solution, the basic idea behind the algorithm design is: 1. Divide the set S of n points by some point mid S into two sets S1 and S2 such that p