Assigned:
Wed 19 Sep 2012
Due:
Wed 26 Sep 2012
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: 6 of the following 7 problems
Points: 18 pts per problem
Suppose that you are given the task of devising an algorithm for
sorting n records and that the basic operation in your
algorithm is an exchange: Exchange[i,j]
swaps the data records in positions i and j.
(Bubble-sort, Insertion-sort, Heapsort, Quicksort, and Shell-sort
are all examples of such algorithms.) The width of an
exchange is defined to be the distance across which data records
are moved, i.e., j - i for
Exchange[i,j]
. Prove that any algorithm for sorting
which uses only constant width exchanges must run in
Omega(n2) time in the worst
case.