CSC263H1, Fall 2019 Problem Set 4 Sample Solutions
CSC263H1: Problem Set 4 Sample Solutions
Due Tuesday October 15 before 10pm
Note: solutions may be incomplete, and meant to be used as guidelines only. We encourage you to ask follow-up questions on the course forum or during office hours.
1. [10 marks] Open Address Hashing.
(a) [2 marks] What is the worst-case running time for Insert in an open-addressing hash table with n items and m slots (m > n)? Give an exact expression in terms of the number of slots of the array that are visited.
(b) [4 marks] Specify a sequence of n + 1 keys, a hash function, and a type of probing such that after inserting each key in the sequence into an initially empty hash table, the (n + 1)-th Insert achieves the worst-case running time given in (a).
(c) [3 marks] What is the average-case running time of each Insert in the sequence from (b)? (By average, we mean the total running time of all calls to Insert, divided by number of such calls.)
Solution
When inserting a new element into a hash table containing n elements, you might have to probe through all of the filled slots in the hash table before you find an open slot. In this situation, you will visit n + 1 slots.
Solution
Consider the sequence of keys (0, 1, 2, · · · , n), where our array is indexed starting at 0. Let h(k) = 0 and let’s say we are using linear probing. After inserting the first n elements, slots 0,1,···,n−1arefull. Wenowtrytoinsertthelastkey,n: sinceh(n)=0,weprobethrough all the filled slots until we find slot n, where we can insert n.
Solution
Inserting key i, for 0 ≤ i ≤ n, from (b) requires accessing i + 1 slots in the array. Therefore the
n n+1 (n+1)(n+2) total sequence cost is i+1 = i = 2
i=0 i=1 cost is (n+1)(n+2) = n+2.
2(n+1) 2
. There are n+1 inserts, so the average
(d) [1 mark] Change just the hash function so that every Insert from the sequence of insertions in part (b) takes constant time.
Page allowance: Please neatly present your solution using 1–2 pages. Any additional pages will not be marked.
Solution
If we set h(k) = k mod m, then there will be no collisions.
Page 1/1