Java Reference
In-Depth Information
9.9 Write an algorithm to implement the move-to-front self-organizing list heuri-
stic, assuming that the list is implemented using an array. In particular, write
a function
MoveToFront
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 beginning of the list.
9.10 Write an algorithm to implement the transpose self-organizing list heuristic,
assuming that the list is implemented using an array. In particular, write
a function
Transpose
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.
9.11 Write functions for computing union, intersection, and set difference on ar-
bitrarily long bit vectors used to represent set membership as described in
Section 9.3. Assume that for each operation both vectors are of equal length.
9.12 Compute the probabilities for the following situations. These probabilities
can be computed analytically, or you may write a computer program to gen-
erate the probabilities by simulation.
(a) Out of a group of 23 students, what is the probability that 2 students
share the same birthday?
(b) Out of a group of 100 students, what is the probability that 3 students
share the same birthday?
(c) How many students must be in the class for the probability to be at least
50% that there are 2 who share a birthday in the same month?
9.13 Assume that you are hashing key K to a hash table of n slots (indexed from
0 to n 1). For each of the following functions h(K), is the function ac-
ceptable as a hash function (i.e., would the hash program work correctly for
both insertions and searches), and if so, is it a good hash function? Function
Random(n)
returns a random integer between 0 and n 1, inclusive.
(a) h(k) = k=n where k and n are integers.
(b) h(k) = 1.
(c) h(k) = (k + Random(n)) mod n.
(d) h(k) = k mod n where n is a prime number.
9.14 Assume that you have a seven-slot closed hash table (the slots are numbered
0 through 6). Show the final hash table that would result if you used the
hash function h(k) = k mod 7 and linear probing on this list of numbers:
3, 12, 9, 2. After inserting the record with key value 2, list for each empty
slot the probability that it will be the next one filled.
9.15 Assume that you have a ten-slot closed hash table (the slots are numbered 0
through 9). Show the final hash table that would result if you used the hash
function h(k) = k mod 10 and quadratic probing on this list of numbers:
3, 12, 9, 2, 79, 46. After inserting the record with key value 46, list for each
empty slot the probability that it will be the next one filled.
