## Description

Q1 Consider the following hash function with separate chaining: it takes a non-negative

integer n < 100000 and calculates its hash value as (2d1 + 3d2 + 5d3 + 7d4 + 11d5)%47,

where % is modulo division, d1 is the most significant digit, and d5 is the least significant

one (and the others are in decreasing significance order). Suppose we have 2000 numbers.

Prove that there exists a number x between 0 and 46 for which we can find at least 43

numbers among the given 2000, whose hash value is exactly x. [2 marks]

Q2 Design a data type that supports the following operations: insert, delete the maximum,

and delete the minimum (all in logarithmic time); and find the maximum and find the

minimum (both in constant time). Hint: Use two heaps. Describe your solution in either

pseudocode (preferred) or English. You can refer to helper functions from the lectures.

Your answer should include a brief explanation why your data type achieves the desired

complexity. [3 marks]

Q3 (a) Implement Quick-Union (without the weighted heuristic or path-compression) in Java.

Use your implementation to create a graph with 256 vertices A (numbered 0 to 255).

Connect the vertices A[i] with A[i + 1] for i ranging from 0 to (and including) 254 by

increments of 2. Connect the vertices A[j] with A[j + 3] for i ranging from 0 to (and

including) 200 by increments of 3. How many connected components are there in the

resulting graph? What is the root of node 19, i.e. what is Find(19)? What is Find(112)?

[3 marks]

(b) Now implement Weighted Quick-Union (without path compression), correctly keeping

track of the size (i.e. the number of elements) of the sub-trees and always merging the

smaller tree into the larger one during Union. Generate the same graph as before. What

are the root elements of nodes 19 and 112? [2 marks]

(You should provide both implementations as part of your submission for this question.)

Q4 Explain how one can modify any sorting algorithm to have O(n) best case time complexity.

[1 marks]

Q5 Describe how an unstable sorting algorithm can be turned into a stable sorting algorithm.

[1 marks]

Q6 Write down in pseudocode a recursive version of the Selection Sort algorithm and write

down the recurrence relation for its worst-case running time. [3 marks]

1