CompSci 161, Fall 2015, Homework 3

  1. [Modified from Goodrich & Tamassia R-8.4-5] Consider the modification of the deterministic version of the quick-sort algorithm so that, instead of selecting the last element in an $n$-element sequence as the pivot, we choose the element at index $\lfloor n/2\rfloor$, that is, an element in the middle of the sequence.

    1. What is the running time of this version of quick-sort on a sequence that is already sorted? Use $O$-notation; you do not need to explain your answer.

    2. Describe an input sequence that would cause this version of quick-sort to run in $\Theta(n^2)$ time.

  2. [Modified from Goodrich & Tamassia R-8.7] Suppose that the in-place quicksort algorithm (Algorithm 8.9 in the textbook, or the same algorithm as presented in class) is executed on a sequence with duplicate elements. What happens in the partition step when all the elements of the input sequence are equal?

  3. [Modified from Goodrich & Tamassia A-8.1] Suppose that you are given a new hardware device that can merge $k>2$ different sorted lists of total size $n$ into a single sorted list in $O(n)$ time, independent of the value of $k$. Show that you can use this device to sort $n$ elements in $O(n\log n/\log k)$ time. (Hint: you may use the fact that $\log_k n=\log n/\log k$.)

  4. Define the "first drop problem", on an input array $A$ of $n$ numbers, to be the problem of finding the first position at which one number drops to a smaller number after it. More formally, the output should be the smallest index $i$ for which $A[i]>A[i+1]$, or $i=n-1$ if no such index exists. For instance, on the input $[5,9,2,4,1]$ the output should be $1$, because the first drop is from the values $9$ to $2$, and the value $9$ occurs at position $A[1]$. But on the input $[1,2,4,5,9]$ there is no first drop and the output should be $4$. You may assume that no two input numbers are equal.

    1. When $n=4$, how many different outcomes does the first drop problem have?

    2. Based only on your answer to part (a), and the $\lceil \log_2(\text{# outcomes})\rceil$ lower bound on the height of any binary comparison tree, how many comparisons would be necessary to correctly solve the first drop problem for $n=4$?

    3. Draw a comparison tree that uses as few comparisons as possible (in the worst case) to solve the first drop problem for $n=4$. How many comparisons in the worst case does your tree use?