The median of an array is defined to be the value of the "middle" element, if there are an odd number of elements, and otherwise the average of the two middle elements. Thus the median of A = {18, 14, 23, 11, 19} is 18. For simplicity right now, we'll assume the array has an odd number of elements and that the array starts with A[0].

1. Give a simple Θ(n*log(n)) algorithm to determine the median of any array.

2. Consider an array with 13 elements: {16, 19, 9, 5, 13, 8, 7, 4, 21, 2, 6, 11, 18}. We want to find its median.

   To find the median, we are going to apply your text's partition algorithm to this array and then repeatedly to subarrays of it, more or less as with quicksort. At each stage, however, we focus on only one side of the partition (one side of the pivot) and ignore the other side. Below is an example.

   Each stage (row) below labeled "Partition" is the result of an entire application of Partition, all its steps. After completing the partition, the pivot is colored red.

   Each stage (row) below labeled "Subarray" focuses on one side of the partition and puts parentheses around the numbers on the other side. Once numbers have parentheses around them, they are ignored from then on.

   The middle location of the array is marked with a hat ^.

   | ^ | 0 1 2 3 4 5 6 7 8 9 10 11 12 -----------|------------------------------------------------------------------ Array | 16 19 9 5 13 8 7 4 21 2 6 11 18 | Partition 1| 16 9 5 13 8 7 4 2 6 11 18 19 21 | Subarray 1 | 16 9 5 13 8 7 4 2 6 11 (18) (19) (21) | Partition 2| 9 5 8 7 4 2 6 11 16 13 (18) (19) (21) | Subarray 2 | 9 5 8 7 4 2 6 (11) (16) (13) (18) (19) (21) | Partition 3| 5 4 2 6 9 8 7 (11) (16) (13) (18) (19) (21) | Subarray 3 | (5) (4) (2) (6) 9 8 7 (11) (16) (13) (18) (19) (21) | Partition 4| (5) (4) (2) (6) 7 8 9 (11) (16) (13) (18) (19) (21) | Subarray 4 | (5) (4) (2) (6) (7) 8 9 (11) (16) (13) (18) (19) (21) | Partition 5| (5) (4) (2) (6) (7) 8 9 (11) (16) (13) (18) (19) (21) |

3. From the table above, is it obvious that we have found the median? What is the value of the median?

4. What determines which side of the partition we keep and which side we ignore above?

5. The algorithm continues repeatedly until the new pivot is located in the middle element. This could occur early on. Give a simple alteration of the order of the numbers in the array above so that the algorithm terminates after the first partition. (Keep the array the same size and mostly the same.)

6. Give an argument that the algorithm terminates with the correct median value.

7. Write your own program to find the median of an array with an odd number of elements as above. You should base your program on the "minimal" quicksort code found in quicksort. I only want code that will work for this particular instance (array of an odd number of integers), and I don't want you to adapt a median-finding algorithm from some other source. Test your program with the given array, and with the array A = {43,22,51,19,11,67,13,36,32,49,28,15,38}; (the same size). Of course this program should not sort the array and should run in time Θ(n).

8. Suppose the array length is anything, either odd or even, and suppose you want to find the value of the ith element in the array, for i = 0, 1, 2, ..., A.length-1. (In the examples above, we were finding the 6th element's value.) Modify your program so that it will find the ith element's value for i in the proper range. Test your modified program with each of the two sets of data and with i = 9. (Again the program should not sort the data.)

9. What are you finding when i = 0? What are you finding when i = A.length-1? Would it be interesting to have an Θ(n) algorithm for these two cases?