Plan
School of Computing and Information Systems COMP90038 Algorithms and Complexity Tutorial Week 10
1–5 October 2018
This week your priority is probably Assignment 2, but don’t ignore the following exercises.
The exercises
67. Use Horspool’s algorithm to search for the pattern GORE in the string ALGORITHM.
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?
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
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?
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.
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.
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.