1. (Divide and Conquer - 20 points) Recall that the Euclidean distance between a pair of points (-1, y1) and (22, 92) is defined as d{(11,41), (22, y2)) = V(x1 - 12) + (41 32). In this question, you are given n > 3 points in the Euclidean 2D space specified by two arrays X[1...),Y[1..n), where (X[],Y[:]) are the coordinates of the ith point. Moreover, you are promised that all c-coordinates and all y-coordinates are distinct. Your goal is to design an efficient divide and conquer algorithm to find three dis- tinct points i, j, k such that the perimeter of the triangle formed by these three points is as small as possible. In other words, find three distinct i, j, k so as to minimize (((X[i],Y[i]), (X[],YG1) + d((x(j),Y(3), (X[k],Y[k]))+d((X[k],Y[k]), (X[1],[)). Follow the steps below: (a) (1 point) Which of the problems described in the lecture notes on divide and conquer is this question most similar to? (b) (6 points) Prove the following claim: (*) Suppose 8 >0 and consider an axis-aligned rectangle of size 8 x 28 (the 28 side is parallel to the I-axis). It can be thought of as two squares, left and right, of sizes 8 x 8 side-by-side. If this rectangle contains at least 1299 points then either the left square or the right square contains a triangle formed by some of these points of perimeter less than 8. Hint: consider splitting the rectangle into sub-squares, each of size 8 (c) (6 points) Describe your divide-and-conquer algorithm in plain English. Be sure to explain what the divide phase is and what the conquer phase is. Do not forget the base case. Be precise. State how the algorithm is different from the one given to the problem you mentioned in part (a). (d) (4 points) Provide a brief argument of correctness for your algorithm based on part (b). /Note: you can attempt this part even if you don't know how to prove the statement in part (6).) (e) (3 points) State the recurrence for the running time of your algorithm, justify it, and solve it. Can you improve this running time? 1. (Divide and Conquer - 20 points) Recall that the Euclidean distance between a pair of points (-1, y1) and (22, 92) is defined as d{(11,41), (22, y2)) = V(x1 - 12) + (41 32). In this question, you are given n > 3 points in the Euclidean 2D space specified by two arrays X[1...),Y[1..n), where (X[],Y[:]) are the coordinates of the ith point. Moreover, you are promised that all c-coordinates and all y-coordinates are distinct. Your goal is to design an efficient divide and conquer algorithm to find three dis- tinct points i, j, k such that the perimeter of the triangle formed by these three points is as small as possible. In other words, find three distinct i, j, k so as to minimize (((X[i],Y[i]), (X[],YG1) + d((x(j),Y(3), (X[k],Y[k]))+d((X[k],Y[k]), (X[1],[)). Follow the steps below: (a) (1 point) Which of the problems described in the lecture notes on divide and conquer is this question most similar to? (b) (6 points) Prove the following claim: (*) Suppose 8 >0 and consider an axis-aligned rectangle of size 8 x 28 (the 28 side is parallel to the I-axis). It can be thought of as two squares, left and right, of sizes 8 x 8 side-by-side. If this rectangle contains at least 1299 points then either the left square or the right square contains a triangle formed by some of these points of perimeter less than 8. Hint: consider splitting the rectangle into sub-squares, each of size 8 (c) (6 points) Describe your divide-and-conquer algorithm in plain English. Be sure to explain what the divide phase is and what the conquer phase is. Do not forget the base case. Be precise. State how the algorithm is different from the one given to the problem you mentioned in part (a). (d) (4 points) Provide a brief argument of correctness for your algorithm based on part (b). /Note: you can attempt this part even if you don't know how to prove the statement in part (6).) (e) (3 points) State the recurrence for the running time of your algorithm, justify it, and solve it. Can you improve this running time
