CSCI 311 -- Algorithms and Data Structures

Homework 4 - Problem Set

15 Points
Due Friday 25 October 2019

This problem set will give you practice on a variety of problems that might show up on the next exam. I have linked a sheet you can print and use for your answers to questions 2 and 3.
  1. (3 points) Show the stages in sorting the keys below using (least-significant-digit) radix sort:
    619
    426
    242
    326
    258
    315
    590
  2. (6 points) Consider hashing the following sequence of values into a hash table with 7 slots (i.e., m = 7) using the hash function h(k) = k%7. For each value, state its hash value, show the table after it is inserted, and state the number of collisions involved in inserting that value using linear probing (count each probe of a filled table slot as a collision):

    11    20    4    12    17    21

  3. (6 points) Repeat the preceding problem, but use double hashing instead of linear probing. Use h2(k) = (k%6)+1 as your second hash value, and state the hash value, second hash value, and number of collisions as well as showing the hash table after each insertion.

Write up your answers and hand them in.