CSC 477/677 Assignment 4

Due date, October 10, 2002, 5:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper. Write your name on each sheet, and do not fold the pages or crimp the corners. Turn the pages in to me or to the graduate assistant on the due date.

  1. Use the median finding algorithm to design a version of quicksort that takes O(n log n) time in all cases.
    Your algorithm should be described in handwritten form turned in on paper, rather than as a written program.
  2. We saw in class that any comparison-based sorting algorithm requires Omega(n log n) time in the worst case. But it might be possible to get a faster sorting algorithm in special cases, such as if the array is already "almost" sorted.
    Suppose we know in advance that our input array will always have runs of length two or more. That is, no three consecutive items are in reverse order. Can you design a comparison-based sorting algorithm which takes only O(n) time in this situation?
  3. (Other problems .... )

Back to Course Page