Java Reference
In-Depth Information
(a) Assume that the input is a list of integers. Design an algorithm that is
linear in the number of integer-integer comparisons in the worst case
that will find and report the majority if one exists, and report that there
is no majority if no such integer exists in the list.
(b) Assume that the input is a list of elements that have no relative ordering,
such as colors or fruit. So all that you can do when you compare two
elements is ask if they are the same or not. Design an algorithm that is
linear in the number of element-element comparisons in the worst case
that will find a majority if one exists, and report that there is no majority
if no such element exists in the list.
15.13 Given an undirected graph G, the problem is to determine whether or not G
is connected. Use an adversary argument to prove that it is necessary to look
at all (n
2
n)=2 potential edges in the worst case.
15.14
(a) Write an equation that describes the average cost for finding the median.
(b) Solve your equation from part (a).
15.15
(a) Write an equation that describes the average cost for finding the ith-
smallest value in an array.
This will be a function of both n and i,
T(n;i).
(b) Solve your equation from part (a).
15.16 Suppose that you have n objects that have identical weight, except for one
that is a bit heavier than the others. You have a balance scale. You can place
objects on each side of the scale and see which collection is heavier. Your
goal is to find the heavier object, with the minimum number of weighings.
Find and prove matching upper and lower bounds for this problem.
15.17 Imagine that you are organizing a basketball tournament for 10 teams. You
know that the merge insert sort will give you a full ranking of the 10 teams
with the minimum number of games played. Assume that each game can be
played in less than an hour, and that any team can play as many games in
a row as necessary. Show a schedule for this tournament that also attempts
to minimize the number of total hours for the tournament and the number of
courts used. If you have to make a tradeoff between the two, then attempt to
minimize the total number of hours that basketball courts are idle.
15.18 Write the complete algorithm for the merge insert sort sketched out in Sec-
tion 15.7.
15.19 Here is a suggestion for what might be a truly optimal sorting algorithm. Pick
the best set of comparisons for input lists of size 2. Then pick the best set of
comparisons for size 3, size 4, size 5, and so on. Combine them together into
one program with a big case statement. Is this an algorithm?
