COMP2011 Tutorial Exercises, Week 13

Tutorial Questions

1. R-8.4 Draw the 11-item hash table that results from using the hash function

h(i) = (2i+5) mod 11

to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 and 5, assuming collisions are handled by chaining.

R-8.5 What is the result of the previous exercise, assuming collisions are handled by linear probing?

R-8.7 What is the result of Exercise R-8.4 assuming collisions are handled by double hashing, using the secondary hash function

h'(k) = 7 - (k mod 7) ?

2. R-10.7,8: Consider a version of the quick-sort algorithm for which, in an n-element sequence, the "middle" element (at index n/2) is chosen as pivot. What is the running time of this algorithm on a sequence that is already sorted? Describe the kind of sequence that would cause this version of quick-sort to run in O(n2) time.

3. Suppose we are given a sequence S of n elements, each of which is coloured red or blue. Assuming S is represented as an array, give an in-place method for ordering S so that all the blue elements are listed before all the red elements. Can you extend your approach to three colours?

4. C-10.11: Suppose we are given an n-element sequence S such that each element in S represents a different vote for class president, where each vote is given as an integer representing the student ID of the chosen candidate. Without making any assumptions about who is running or even how many candidates there are, design an O(n log n)-time algorithm to see who wins the election S represents, assuming the candidate with the most votes wins.

5. C-10.12: Consider the voting problem from the previous exercise, but now suppose that we know the number k < n of candidates running. Describe an O(n log k)-time algorithm for determining who wins the election.