Java Reference
In-Depth Information
A good introduction to this topic is “Dynamic Hashing Schemes” by R.J. Enbody
and H.C. Du [ED88].
9.6
Exercises
9.1 Create a graph showing expected cost versus the probability of an unsuc-
cessful search when performing sequential search (see Section 9.1). What
can you say qualitatively about the rate of increase in expected cost as the
probability of unsuccessful search grows?
9.2 Modify the binary search routine of Section 3.5 to implement interpolation
search. Assume that keys are in the range 1 to 10,000, and that all key values
within the range are equally likely to occur.
9.3 Write an algorithm to find the Kth smallest value in an unsorted array of n
numbers (K <= n). Your algorithm should require (n) time in the average
case. Hint: Your algorithm should look similar to Quicksort.
9.4 Example 9.9.3 discusses a distribution where the relative frequencies of the
records match the harmonic series. That is, for every occurrence of the first
record, the second record will appear half as often, the third will appear one
third as often, the fourth one quarter as often, and so on. The actual prob-
ability for the ith record was defined to be 1=(iH
n
).
Explain why this is
correct.
9.5 Graph the equations T(n) = log
2
n and T(n) = n= log
e
n. Which gives the
better performance, binary search on a sorted list, or sequential search on a
list ordered by frequency where the frequency conforms to a Zipf distribu-
tion? Characterize the difference in running times.
9.6 Assume that the values A through H are stored in a self-organizing list, ini-
tially in ascending order. Consider the three self-organizing list heuristics:
count, move-to-front, and transpose. For count, assume that the record is
moved ahead in the list passing over any other record that its count is now
greater than. For each, show the resulting list and the total number of com-
parisons required resulting from the following series of accesses:
D H H G H E G H G H E C E H G:
9.7 For each of the three self-organizing list heuristics (count, move-to-front, and
transpose), describe a series of record accesses for which it would require the
greatest number of comparisons of the three.
9.8 Write an algorithm to implement the frequency count self-organizing list
heuristic, assuming that the list is implemented using an array. In particu-
lar, write a function
FreqCount
that takes as input a value to be searched
for and which adjusts the list appropriately. If the value is not already in the
list, add it to the end of the list with a frequency count of one.
