Fundamental Algorithms
Homework #7

Due Date: March 29

  1. Below is a probabilistic Algorithm for finding the k-th smallest key in a list of n keys. |S| denotes the number of elements in a list S.
     Procedure Select (k,S):
     If |S| <  k  then return "error" else
         choose RANDOMLY an element a from S; Let S1,S2, and S3 be the keys in
         S less than, equal to, and greater than a, respectively;
         If |S1| >= k then return Select (k,S1)
         else If |S1|+|S2| >= k then return a
              else return Select (k-|S1|-|S2|, S3)
    Notice that it is possible to have equal keys in the list. Let T(n) be the compexity of the above procedure (counting comparisons only). Clearly T(1)=1. Assume , for simplicity, that all keys are duistinct and show, for n>=2, that the AVERAGE value of T(n) satisfies the following inequality: T(n)<=c*n + max(k){(1/n)*[(Sumation from i=n-k-1 to i=n-1 of T(i)) + (Sumation from i=k to i=n-1 of T(i))]} Show that T(n) <= 4*c*n for all n>=2.

  2. Consider a rectangular array. Sort the elements in each row into increasing order. Next sort the elements in each column into increasing order. Show that the elements in each row remain sorted.

  3. n keys are located in n consecutive memory locations. We want to sort them by a nonadaptive algorithm, with no extra memory required for the keys, based solely on the primitive operation CEX ("compare-exchange") defined below: For 1<=i,j<=n CEX(i,j) compares the i and j keys and resets them so that the maximal key occupies the maximum of i,j location and the minimal key occupies the minimum of i,j location.

    a. Write a program to sort 4 keys,6 keys and 8 keys. Try to minimize the number of CEX operations used. No recursion or conditionals (loops) allowed. Example: CEX(1,2);CEX(2,3);CEX(1,2) Sorts 3 integers

    b.Write a CEX-program to sort n integers (minimize CEX operations)

    c. How many CEX instructions does your program in (b) above use as a function of n?

  4. 4.a. Modify the (crude) Quicksort algorithm given in class as follows: The new algorithm will use an extra stack. In each round, after splitting the list which is to be sorted into 3 parts L1,P,L2, the left list the pivot and the right list respectively, the new algorithm will do the following

    (i) Stack the delimiting indices of one of the sublists L1 or L2.

    (ii) If the remaining list ( whose delimiting indices was not stacked) has 2 or more keys then apply, recursively, the algorithm on this list. Otherwise pop the stack. If the stack is emply then return and halt. Else apply the algorithm , recursively , on the sublist defined by the popped indices.

    4.b Which of L1 and L2 would you choose to stack at each round?

    4.c How large could the stack get during the intermediary steps of your algorithm?