
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.

-
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.
-
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?
-
(Other problems .... )

Back to
Course Page