b. The Boyer-Moore algorithm must compare the remaining −1char–
10. n/a
11. a. The following brute-force algorithm is based on straightforward check-
ing of the circular shift definition.
Algorithm RightCyclicShift([0 −1][0 −1])
The algorithm uses no extra space, and its time efficiency is clearly (2)
(It’s Θ(2)in the worst case.)
b. A more time-efficient algorithm is to append the (−1)-character prefix
14
Exercises 7.3
1. For the input 30, 20, 56, 75, 31, 19 and hash function ()=mod 11
a. construct the open hash table.
2. For the input 30, 20, 56, 75, 31, 19 and hash function ()=mod 11
a. construct the closed hash table.
3. Whyisitnotagoodideaforahashfunctiontodependonjustoneletter
(say, the first one) of a natural-language word?
4. Find the probability of all keys being hashed to the same cell of a hash
table of size if the hash function distributes keys evenly among all the
cells of the table.
6. Answer the following questions for the separate-chaining version of hash-
ing.
a. Where would you insert keys if you knew that all the keys in the
dictionary are distinct? Which dictionary operations, if any, would ben-
efitfromthismodification?
8. Fill in the following table with the average-case (as the first entry) and
worst-case (as the second entry) efficiency classes for the five implemen-
tations of the ADT dictionary:
unordered
array
ordered
array
binary
search
tree
balanced
search
tree
hashing
9. We have discussed hashing in the context of techniques based on space—
time trade-offs. But it also takes advantage of another general strategy.
Which one?
16
Hints to Exercises 7.3
1. Apply the open hashing (separate chaining) scheme to the input given as
2. Apply the closed hashing (open addressing) scheme to the input given as it
3. How many different addresses can such a hash function produce? Would
it distribute keys evenly?
5. Find the probability that people have different birthdays. As to the
hashing connection, what hashing phenomenon deals with coincidences?
6. a. There is no need to insert a new key at the end of the linked list it is
hashed to.
b. Which operations are faster in a sorted linked list and why? For
sorting, do we have to copy all elements in the nonempty lists in an array
Solutions to Exercises 7.3
1. a.
The list of keys: 30, 20, 56, 75, 31, 19
b. The largest number of key comparisons in a successful search in this
table is 3 (in searching for =31).
2. a.
The list of keys: 30, 20, 56, 75, 31, 19
The hash function: ()=mod 11
0 1 2 34567 8 9 10
30
30 20
6·1+1
6·1+1
6·1+1
6·2+1
6·3+1
6·6=14
6≈23
18
3. The number of different values of such a function would be obviously
4. The probability of all keys to be hashed to a particular address is equal
to ¡1
¢Since there are different addresses, the answer is ¡1
¢=
1
−1
5. The probability of people having different birthdays is 364
365
363
365 ··· 365−(−1)
365
The smallest value of for which this expression becomes less than 0.5 is
23. Sedgewick and Flajolet [SF96] give the following analytical solution
to the problem:
6. a. If all the keys are known to be distinct, a new key can always be inserted
at the beginning of its linked list; this will make the insertion operation
Θ(1)This will not change the efficiencies of search and deletion, however.
b. Searching in a sorted list can be stopped as soon as a key larger than
19
7. Insert successive elements of the list in a hash table until a matching
element is encountered or the list is exhausted. The worst-case efficiency
8. In each cell of the table, the first and second entries are the average-case
and worst-case efficiencies, respectively.
unordered
array
ordered
array
binary
search
tree
balanced
search
tree
hashing
9. Representation change–one of the three varieties of transform-and-conquer.
Exercises 7.4
1. Give examples of using an index in real-life applications that do not involve
computers.
2. a. Prove the equality
3. Find the minimum order of the B-tree that guarantees that the number of
disk accesses in searching in a file of 100 million records does not exceed
3. Assume that the root’s page is stored in main memory.
6. a. A top-down 2-3-4 tree is a B-tree of order 4 with the following
modification of the insert operation. Whenever a search for a leaf for a
new key encounters a full node (i.e., a node with three keys), the node is
7. a. BWrite a program implementing a key insertion algorithm in a B-tree.
21
Hints to Exercises 7.4
1. Thinking about searching for information should lead to a variety of ex-
amples.
4. Follow the insertion algorithm outlined in the section.
5. The algorithm is suggested by the definition of the B-tree.
6. a. Just follow the description of the algorithm given in the statement of
1. Here are a few common examples of using an index: labeling drawers of a
file cabinet with, say, a range of letters; an index of a book’s terms indicat-
2. a.
1+
−1
X
=1
2d2e−1(d2e−1) + 2d2e−1
b. The inequality
≥4d2e−1−1
is equivalent to +1
23
3. If the tree’s root is stored in main memory, the number of disk accesses
will be equal to the number of the levels minus 1, which is exactly the
height of the tree. So, we need to find the smallest value of the order
4. Since there is enough room for 30 in the leaf for it, the resulting B-tree
will look as follows
20 51
5. Starting at the root, follow the chain of the rightmost pointers to the
(rightmost) leaf. The largest key is the last key in that leaf.
24
10
10
6
6, 10 6, 10, 15
15, 31
10
615, 20, 31
b. The principal advantage of splitting full nodes (4-nodes with 3 keys)
on a way down during insertion of a new key lies in the fact that if the
The disadvantage of splitting full nodes on the way down lies in the fact
that it can lead to a taller tree than necessary. For the list of part (a),
7. n/a
25