## Description

Ve281 Data Structures and Algorithms

Written Assignment Two

The assignment consists of five problems.

1. Sort 3, 7, 4, 1, 8, 9, 2, 6, 5, 10 using quick sort. The pivot is chosen as the median

of the first, the middle (or the left-to-middle element if the array size N is even), and

the last element. Use the in-place partitioning strategy discussed in class (Note that

you should swap the selected pivot with the first element of the array as the first step

of the partitioning). Assume that if the subarray size is less than or equal to three,

insertion sort will be called to sort the subarray. Show the intermediate steps, such

as the pivot you choose, the array after partitioning, etc. Do not just write the final

sorted result.

2. Apply radix sort to sort the sequence of decimal numbers 189, 479, 032, 538, 446, 526,

943, 738, 632, 379. Show the intermediate steps. Do not just write the final sorted

result.

3. In the deterministic linear-time selection algorithm, instead of partitioning all the

inputs into a number of groups of size 5, we partition the inputs into a number of

groups of size 7. The rest steps of the algorithm are similar to the original version.

Will the runtime of this new algorithm still be O(n), where n is the input size? Prove

your claim.

4. Given a sequence of inputs 4371, 1323, 6173, 4199, 4344, 9679, 1989, insert them into a

hash table of size 10. Suppose that the hash function is h(x) = x%10. Show the result

for the following implementations:

(a) Hash table using separate chaining. Assume that the insertion is always at the

beginning of each linked list.

(b) Hash table using linear probing.

(c) Hash table using quadratic probing.

(d) Hash table using double hashing, with the second hash function as h2(x) = (7 − x)%7.

5. Show the result of rehashing the four hash tables in the Problem 4. Rehash using a new

table size of 19, and a new hash function h(x) = x%19. (Hint: The order in rehashing

depends on the order stored in the old hash table, not on their initial inserting order.)

1