The following is slide 8 of slide set 7

The question is

For part 1, we also need to proof the correctness by induction, and proof the time complexity.

The following is the clarification on the problem

For Q1.3 Closed form means closed form in the sense that T(n) is written in terms of n without any additional recursive call to T

Min and Max with (3n/2)2 comparisons: [ For convenience we assume n is even ] - Put the n input items in a stack S, and initialize two other stacks ("Low" and "High") to be empty - Pop the top two from S, compare them, push the smaller on stack Low and the larger on stack High - Repeat until S is empty (happens after n/2 comparisons) - The n/2 integers on Low are candidates for Min but not for Max: Find their smallest, output it as the Min - This takes (n/2)-1 comparisons - The n/2 integers on High are candidates for Max but not for Min: Find their largest, output it as the Max - This takes (n/2)-1 comparisons Question 1. (25 points) Recall that we covered in class the "simultaneous minimum and naximum" problem (slide 8 of slide set 7 ). This question explores a different algorithm for hat problem. 1. (5 points) Assuming n is a power of 2, give a recursive divide-and-conquer algorithm for solving this problem (with recursion tree of depthlogn ). 2. (5 points) If we let T(n) denote the number of comparisons done by your algorithm, write down the recurrence relation satisfied by T(n); take the bottom of the recursion to be for n=2, and write down both T(2) and the recurrence relation for n>2. 3. (15 points) Solve exactly (without using the "big O" notation) the recurrence relation for T(n); give an exact count of the number of comparisons as a function of n. How does your answer compare to the number of comparisons taken by the algorithm covered in class? - Your job in Q1.2 is to set up a recurrence relation. In Q1.3, you then find the closed-form solution of the recursive equation you found in Q1.2 exactly without using any asymptotic notations. See @166. It is a lot simpler than what that post says, though