(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 5  Heapsort, Median, Etc.     Partial Answers

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 {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. [Any sorting algorithm with guaranteed Θ(n*log(n)) time will work here, such as mergesort or heapsort. You sort into order and select the value of the middle element. Quicksort does not have guaranteed Θ(n*log(n)) performance and so doesn't satisfy this question, though as we know a randomized version would be a good choice in practice.]

2. Consider an array with 13 elements: {16, 19, 9, 5, 13, 8, 7, 4, 21, 2, 6, 11, 18}. What is its median? [We see below that the median is 9, but if we sort this list the middle element A[6] is seen to be 0.]

           |                                  ^
           |    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. What determines which side of the partition we keep and which side we ignore above? [In each case we are keeping the portion of the partition that contains the middle index 6.]

4. 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 array above so that the algorithm terminates after the first partition. (Keep the array the same size and mostly the same.) [If we interchange A[2] with A[12] (that is, stick the median value in the pivot position), then the algorithm terminates after one call to partition. This is because the termination condition is for A[6] to equal the pivot.]

5. Give an argument that the algorithm terminates with the correct median value. [As in question 4 above, the algorithm terminates when A[6] is equal to the pivot. At this point all A[i] for i < 6 must be < A[6] and all A[i] for i > 6 must be > A[6]. This is the definition of median. Note that we have the median even though the array will not usually be in sorted order, that is, we haven't (usually) completely sorted the array, but we've still gotten it split at the median.]

6. This algorithm has expected performance of Θ(n), assuming a random pivot is chosen at each stage. (The proof of this average performance is beyond the scope of this course [text, pages 215-219.) Assume that the subarray selected at each stage is of length at most 3/4 times the length of the previous subarray. Give a recurrence relation for this case. Using the recursion tree approach, argue carefully that in this special case this is a Θ(n) algorithm. [Here is what the recursion tree looks, with one node at each level, since we stick with one side of each partition:

   Tree Cost ^ n ----> c n | | | (3/4) n ----> c (3/4) n log4/3(n) = | | (3/4)^2 n ----> c (3/4)2 n log2(n) / log2(4/3) = | | (3/4)^3 n ----> c (3/4)3 n 3.47606 log2(n) | | ... 1 ----> c | v

   So the height of the tree is 3.47606*log₂(n), and the total cost is given by:
   Total Cost = c n + c (3/4) n + c (3/4)² n + c (3/4)³ n + ... + c n
   <= c n (1 + (3/4) + (3/4)² + (3/4)³ + ...) = c n (1/(1-(3/4))) = 4 c n

   The cost is a constant times n, and the algorithm is Θ(n).

   At least one student argued that because the cost is tending to 0 as one goes down the tree, this makes it Θ(n). This is not correct, as one can see if the subarray selected at each stage was 1 less than the previous subarray. Then the total height would be n, and the total cost would be cn + c(n-1) + c(n-2) + ... c = c n(n+1)/2 = Θ(n²).]

7. Write your own program from scratch to find the median of an array with an odd number of elements as above. You can use the code for partitioning 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 first with the array above, and then with: {43,22,51,19,11,67,13,36,32,49,28,15,38}. (I worked hard so that the output of my program didn't look too (searching for adjective here ...) You don't need to do this.)

// Median.java: finds median value
public class Median {

   public int median(int[] A, int p, int r,
         int mid) {
      printa(A, p, r);
      int pivot = partition(A, p, r);
      printa(A, p, r);
      if (mid == pivot) return A[mid];
      else if (mid < pivot)
         return median(A, p, pivot-1, mid);
      else return median(A, pivot+1, r, mid);
   }

   public int partition(int[] A, int p, int r) {
      int x = A[r];
      int i = p - 1;
      for (int j = p; j < r; j++) {
         if (A[j] <= x) {
            i++;
            exchange(A,i, j);
         }
      }
      exchange(A, i+1, r);
      return i + 1;
   }

   private void exchange(int[] A, int i, int j) {
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
   }

   private void printa(int[] A, int p, int r) {
      int i = 0;
      while (i < p) printn2(A[i++]);
      for (i = p; i <= r; i++)
         printn1(A[i]);
      i = r+1;
      while (i <= A.length - 1) printn2(A[i++]);
      System.out.println();
   }

   void printn1(int i) {
      if (i < 10) System.out.print("   " + i + " ");
      else System.out.print("  "  + i + " ");
   }

   void printn2(int i) {
      if (i < 10) System.out.print("  (" + i + ")");
      else System.out.print(" ("  + i + ")");
   }

   public static void main(String[] args) {
      int[] A =
         {43,22,51,19,11,67,13,36,32,49,28,15,38};
      Median med = new Median();
      System.out.println("Median:" + 
         med.median(A,0,A.length-1,(A.length-1)/2));
   }
}

         0 |    0    1    2    3    4    5    6    7    8    9   10   11   12 
-----------|------------------------------------------------------------------
Array      |   43   22   51   19   11   67   13   36   32   49   28   15   38 
           | 
Partition 1|   22   19   11   13   36   32   28   15   38   49   43   51   67 
           | 
Subarray 1 |   22   19   11   13   36   32   28   15  (38) (49) (43) (51) (67)
           | 
Partition 2|   11   13   15   19   36   32   28   22  (38) (49) (43) (51) (67)
           | 
Subarray 2 |  (11) (13) (15)  19   36   32   28   22  (38) (49) (43) (51) (67)
           | 
Partition 3|  (11) (13) (15)  19   22   32   28   36  (38) (49) (43) (51) (67)
           | 
Subarray 3 |  (11) (13) (15) (19) (22)  32   28   36  (38) (49) (43) (51) (67)
           | 
Partition 4|  (11) (13) (15) (19) (22)  32   28   36  (38) (49) (43) (51) (67)
           | 
Subarray 4 |  (11) (13) (15) (19) (22)  32   28  (36) (38) (49) (43) (51) (67)
           | 
Partition 5|  (11) (13) (15) (19) (22)  28   32  (36) (38) (49) (43) (51) (67)
           | 
Subarray 5 |  (11) (13) (15) (19) (22) (28)  32  (36) (38) (49) (43) (51) (67)
           | 
Partition 5|  (11) (13) (15) (19) (22) (28)  32  (36) (38) (49) (43) (51) (67)
           | Median: 32

8. [Because of the mistake below in the statement of this problem, I'll have to leave off grading it.] Suppose the array length is anything, either odd or even, and suppose you want to find the value of the ith element in the sorted [I said "sorted" here by mistake. Of course, if the array is already sorted, or if you sort the array then all of this is trivial, and of time O(n log n)] array, for i = 0, 1, 2, ..., A.length-1. (In the examples above, we were finding the 6th element's value.)

   Assuming the word "sorted" is left out above:
   What are you finding when i = 0? [You would be finding the minimum value of the array in Θ(n) time, which we can do in a simpler fashion.]

   What are you finding when i = A.length-1? [Similarly finding the maximum value in Θ(n) time.]

   What changes would be needed to the intuitive description of this algorithm in order to handle this more general case? [In the first example above, instead of using the index 6 we would use index i. No other changes would be needed.]

9. The above "weird topic" page is incomplete. The directions are: Finish the page up by adding to the end, so that you get something "weird", or at least "interesting", or at least something that you didn't already know. [This link now shows the answer: a high-tech pair of formulas for Fibonacci numbers.]

10. Text, Exercise 6.1-6 on page 154. [Is the array with values {23,17,14,6,13,10,1,5,7,12} a max-heap? If not, why not? Note that these numbers are in array locations A[1], A[2], ... A[10].] [Heap property fails at item A[4] = 6. Need to swap A[4] and A[9] = 7 to restore heap property.]

11. Suppose we used the zero element of our arrays, rather than ignoring it. Give new parent, left and right functions that would work in this case. [But we are not using the zero element in everything below.]
    [int parent(int i) {return (i-1)/2;}
     int left(int i) { return 2*i + 1; }
     int right(int i) { return 2*i + 2; } ]

12. Text, Exercise 6.2-1 on page 156. [Illustrate the operation of Max-Heapify(A,3) on the array A = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}. Is the result a max-heap? If not, why not?
    [after 1st interchange: heapsize:14, heap: 27, 17, 10, 16, 13, 3, 1, 5, 7, 12, 4, 8, 9, 0
     after 2st interchange: heapsize:14, heap: 27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0
    Yes, this is now a max-heap.

13. Text, Exercise 6.2-5 on page 156. [Rewrite the code for Max-Heapify so that it uses an iterative control structure (a loop) instead of recursion. This is an example of removing tail-recursion. It's mostly just a matter of giving the second parameter a new value while you go around a loop again.] [Using exactly your text's algorithm from page 154, here is a simple answer:

    public void maxHeapify2(int[] A, int i) { while(true) { printheap(A); int l = left(i); int r = right(i); int largest; if (l <= heapsize && A[l] > A[i]) largest = l; else largest = i; if (r <= heapsize && A[r] > A[largest]) largest = r; if (largest == i) return; exchange(A, i, largest); i = largest; } }

    [Questions 14 and 15 below somehow got slightly muddled together]

14. Suppose numbers {26, 5, 77, 1, 85, 11, 59, 15, 48, 19} are stored in array locations A[1], ..., A[10]. Build A into a max-heap using the algorithm Build-Max-Heap from the text [page 157] or buildMaxHeap in the program referred to above. (They are the same.) Notice that this starts by calling Max-Heapify(A,5) from the text [page 154] or maxHeapify(A,5) from my program. Then proceed down from 5 to 4 to 3 to 2 to 1. Why not start with 6 instead of 5 above? Show that in this case you get the wrong answer if you start at 1 and work your way up to 5. [This is a little awkward to show in a .txt file, but you can show the action at each step and the resulting array.]
    [Here is the result of each iteration of the loop in buildMaxHeap:

    buildMaxHeap,i: 5;heapsize:10, heap: 26, 5, 77, 1, 85, 11, 59, 15, 48, 19 buildMaxHeap,i: 4;heapsize:10, heap: 26, 5, 77, 48, 85, 11, 59, 15, 1, 19 buildMaxHeap,i: 3;heapsize:10, heap: 26, 5, 77, 48, 85, 11, 59, 15, 1, 19 buildMaxHeap,i: 2;heapsize:10, heap: 26, 85, 77, 48, 19, 11, 59, 15, 1, 5 buildMaxHeap,i: 1;heapsize:10, heap: 85, 48, 77, 26, 19, 11, 59, 15, 1, 5

15. Text, Exercise 6.3-2 on page 159. [Show that the algorithm works in the case above if you start with 6 instead of 5 and work your way down to 1. Show that the algorithm fails in the case above if you start at 1 and work your way up to 5.] [If you start with 6, nothing different happens because, inside maxHeapify, the variables l and r will be greater than heapsize. Going from 1 to 5 in that order almost immediately results in A[1] = 77, A[2] = 85, which is not a heap.]

16. What property does the magic node floor(A.length/2) have? (Notice that in Java, since we have a zero element also, this would be floor((A.length - 1)/2).) [This gives the node with smallest index that has no children.]

17. Text, Exercise 6.4-1 on page 160. [Illustrate the operation of heapsort on the array A = {5,13,2,25,7,17,20,8,4}. (Here again, A[1] = 5.)]
    [Here are the steps involved:

    after buildMaxHeap: heapsize:8, heap: 25, 17, 20, 7, 2, 13, 8, 4, heapsort,after step 8:heapsize:7, heap: 20, 17, 13, 7, 2, 4, 8, 25, heapsort,after step 7:heapsize:6, heap: 17, 8, 13, 7, 2, 4, 20, 25, heapsort,after step 6:heapsize:5, heap: 13, 8, 4, 7, 2, 17, 20, 25, heapsort,after step 5:heapsize:4, heap: 8, 7, 4, 2, 13, 17, 20, 25, heapsort,after step 4:heapsize:3, heap: 7, 2, 4, 8, 13, 17, 20, 25, heapsort,after step 3:heapsize:2, heap: 4, 2, 7, 8, 13, 17, 20, 25, heapsort,after step 2:heapsize:1, heap: 2, 4, 7, 8, 13, 17, 20, 25, heapsize:1, heap: 2, 4, 7, 8, 13, 17, 20, 25,