Java Reference
In-Depth Information
is (log n), that is, do not resort to sequential search once an occurrence of
K is found.
3.18 Given an array storing integers ordered by value, modify the binary search
routine to return the position of the integer with the greatest value less than
K when K itself does not appear in the array. Return ERROR if the least
value in the array is greater than K.
3.19 Modify the binary search routine to support search in an array of infinite
size. In particular, you are given as input a sorted array and a key value
K to search for. Call n the position of the smallest value in the array that
is equal to or larger than X. Provide an algorithm that can determine n in
O(log n) comparisons in the worst case. Explain why your algorithm meets
the required time bound.
3.20 It is possible to change the way that we pick the dividing point in a binary
search, and still get a working search routine. However, where we pick the
dividing point could affect the performance of the algorithm.
(a) If we change the dividing point computation in function binary from
i = (l + r)=2 to i = (l + ((r l)=3)), what will the worst-case run-
ning time be in asymptotic terms? If the difference is only a constant
time factor, how much slower or faster will the modified program be
compared to the original version of binary ?
(b) If we change the dividing point computation in function binary from
i = (l + r)=2 to i = r2, what will the worst-case running time be in
asymptotic terms? If the difference is only a constant time factor, how
much slower or faster will the modified program be compared to the
original version of binary ?
3.21 Design an algorithm to assemble a jigsaw puzzle. Assume that each piece
has four sides, and that each piece's final orientation is known (top, bottom,
etc.). Assume that you have available a function
booleancompare(Piecea,Pieceb,Sidead)
that can tell, in constant time, whether piece a connects to piece b on a's
side ad and b's opposite side bd. The input to your algorithm should consist
of an nm array of random pieces, along with dimensions n and m. The
algorithm should put the pieces in their correct positions in the array. Your
algorithm should be as efficient as possible in the asymptotic sense. Write
a summation for the running time of your algorithm on n pieces, and then
derive a closed-form solution for the summation.
3.22 Can the average case cost for an algorithm be worse than the worst case cost?
Can it be better than the best case cost? Explain why or why not.
3.23 Prove that if an algorithm is (f(n)) in the average case, then it is (f(n))
in the worst case.
Search WWH ::




Custom Search