School of Computing and Information Systems COMP90038 Algorithms and Complexity Tutorial Week 10
Sample Answers
The exercises
67. Use Horspool’s algorithm to search for the pattern GORE in the string ALGORITHM.
Answer: For that pattern we calculate the shifts: S[G] = 3,S[O] = 2,S[R] = 1,S[x] = 4 for all other letters x. So the first shift (when the string’s O fails to match E) is 2 positions, bringing E under the string’s I. The next shift is 4, which will take us beyond the end of the string, so the algorithm halts (after just two comparisons), reporting failure.
68. How many character comparisons does it take Horspool’s algorithm to decided that CAB is not found in ABRACADABRA? How many to find that DRAC is not there?
Answer: Four and six, respectively.
69. How many character comparisons will be made by Horspool’s algorithm in searching for each
of the following patterns it the binary text of one million zeros?
(a) 01001 (b) 00010 (c) 01111
Answer:
(a) The pattern’s last 1 will be compared against every single 0 in the text (except of course the first four), since the skip will be 1. So 999,996 comparisons.
(b) Here we will will make two comparisons between shifts, and each shift is of length 2. So the answer is again 999,996 comparisons.
(c) For the last pattern, the skip is 4. So we will make 249,999 comparisons.
70. Using Horspool’s method to search in a text of length n for a pattern of length m, what does a worst-case example look like?
Answer: Let the text have n zeros and let the pattern be of length ⌈n/2⌉ and consist of a single 1 followed by zeros. Each skip will then be just a single position, and between skips, ⌈n/2⌉ comparisons are made. After the first ⌈n/2⌉ comparisons, we skip ⌊n/2⌋ times. Altogether we have (1+⌊n/2⌋)⌈n/2⌉ comparisons. If n is even, that is (n2+2n)/4 comparisons. If n is odd, it is (n2 + 2n + 1)/4 comparisons.
71. (Optional, only for those who got interested in this non-examinable algorithm.) Draw the finite-state machine that corresponds to the table built by the Knuth-Morris-Pratt method to enable fast search of the string 0011. Trace it as it processes the text 01001000110.
Answer:
10
001021314
10
72. For the input 40, 60, 37, 84, 42, 18, 30, and hash function h(K) = k mod 11,
(a) construct the open hash table (separate chaining).
(b) find the largest number of key comparisons in a successful search in this table.
(c) find the average number of key comparisons in a successful search in this table.
Answer:
(a)
0 1 2 3 4 5 6 7 8 9 10 37 60 40 30 42
84 18
(b) The largest number of probes in a successful search is 3.
(c) The average is 1+1+1+1+1+2+3 = 1.43.
7
73. For the input 40, 60, 37, 84, 42, 18, 30, and hash function h(K) = k mod 11,
(a) construct the closed hash table.
(b) find the largest number of key comparisons in a successful search in this table.
(c) find the average number of key comparisons in a successful search in this table.
Answer:
(a)
0 1 2 3 4 5 6 7 8 9 10 30 37 60 40 84 42 18
(b) The largest number of probes in a successful search is 4.
(c) The average is 1+1+1+1+2+4+4 = 2. 7