Homework 2

CS409 - Spring 2000

Due: Thursday, Feb 10

1. (5 pts) Suppose you're using hashing with chaining and your table size is 11,  What does the table look like after the following items have been inserted: 70, 5, 52, 24, 46, 63, 38, 81?  Assume that new items are added at the end of a list and that your hash function is 
   h(x) = x mod table-size.

    

2. (15 pts) Suppose you have to design a Dictionary that holds 2048 items.
   1. How many probes (i.e., key comparisons) are used for an unsuccessful search if the Dictionary is implemented as a sorted array?  Assume the use of Binary Search.
   2. How large a hashtable do you need if your goal is to have 2 as the expected number of probes for an unsuccessful search?
   3. How much more space is needed by the hashtable compared to the sorted array?  Assume that each pointer in a linked list takes 1 word of storage.

    

3. (10 pts) Suppose we wish to implement a Smaller operation on sets of integers. For example, for a set S, S.Smaller(a) will return all the integers c in S such that c<a. The time for a Smaller operation will be of the form O(X+i) where i is the number of integers in the set that are smaller than a and X is some function that depends on n, the number of items in the set. (We are stuck with i here since it takes that much time just to print the answer to a given Smaller query.) For each of the following data structures, determine the best value of X in the time for a Smaller operation. Give a short explanation of how that time is achieved and why you think that amount of time is required.
   1. Sorted array
   2. Hashtable

    

4. (10 pts) For geometric hashing, the kind of transformation we allow determines the number of points needed to establish a reference frame (i.e., for translation in any dimension, we need just one point; this point is enough to determine the location of our reference frame's origin).  For each of the following transformation types, determine the number of points needed to establish a reference frame.
   1. 2-dimensions, translation and scaling
   2. 2-dimensions, translation, rotation, and scaling
   3. 3-dimensions, translation and scaling
   4. 3-dimensions, translation, rotation, and scaling