Answer Happy

1. (a) W(n) represents the number of operations performed by an algorithm with problem size n. Solve the recurrence equation and state the complexity of the algorithm in 0 notation. W(1) = 0 W(n = 2W(n-1) + 2 (10 marks) (b) A hash table has a size of 13. A key value k is mapped by open addressing as follows: A hashing function j = hash(k) = k mod 13 A double hashing increment d=hashIncr(k)= k mod 7+1 A double hashing function rehash(j, d) = (1 + d) mod 13 Draw the hash table to show how the sequence of data records with key values 9, 23, 35, 17 and 37 are stored in the hash table (starting with an empty table). Write the total number of hashing and rehashing done when each of these records is inserted into the hash table. (15 marks)