Description
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
