Java Reference
In-Depth Information
things by assuming that each game takes less than an hour, and that each team
can be scheduled for a game every hour if necessary. (Note that everything
said here about basketball courts is also true about processors in a parallel
algorithm to solve the maximum-finding problem).
(a) How many basketball courts do we need to insure that every team can
play whenever we want to minimize the total tournament time?
(b) How long will the tournament be in this case?
(c) What is the total number of “court-hours” available? How many total
hours are courts being used? How many total court-hours are unused?
(d) Modify the algorithm in such a way as to reduce the total number of
courts needed, by perhaps not letting every team play whenever possi-
ble. This will increase the total hours of the tournament, but try to keep
the increase as low as possible. For your new algorithm, how long is the
tournament, how many courts are needed, how many total court-hours
are available, how many court-hours are used, and how many unused?
15.3 Explain why the cost of splitting a list of six into two lists of three to find the
minimum and maximum elements requires eight comparisons, while split-
ting the list into a list of two and a list of four costs only seven comparisons.
15.4 Write out a table showing the number of comparisons required to find the
minimum and maximum for all divisions for all values of n 13.
15.5 Present an adversary argument as a lower bounds proof to show that n 1
comparisons are necessary to find the maximum of n values in the worst case.
15.6 Present an adversary argument as a lower bounds proof to show that n com-
parisons are necessary in the worst case when searching for an element with
value X (if one exists) from among n elements.
15.7 Section 15.6 claims that by picking a pivot that always discards at least a
fixed fraction c of the remaining array, the resulting algorithm will be linear.
Explain why this is true. Hint: The Master Theorem (Theorem 14.1) might
help you.
15.8 Show that any comparison-based algorithm for finding the median must use
at least n 1 comparisons.
15.9 Show that any comparison-based algorithm for finding the second-smallest
of n values can be extended to find the smallest value also, without requiring
any more comparisons to be performed.
15.10 Show that any comparison-based algorithm for sorting can be modified to
remove all duplicates without requiring any more comparisons to be per-
formed.
15.11 Show that any comparison-based algorithm for removing duplicates from a
list of values must use (n log n) comparisons.
15.12 Given a list of n elements, an element of the list is a majority if it appears
more than n=2 times.
