Homework 2 Solution

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.
    This is meant to be an easy question.
    0    :
    1:
    2: 24, 46
    3:
    4: 70, 81
    5: 5, 38
    6:
    7:
    8: 52, 63
    9:
    10:

     

  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.
      If the number of items is of the form 2k-1 then a single probe cuts the remaining number to look at to 2(k-1)-1.  Thus a table holding 2047 items would require exactly 11 probes for an unsuccessful search.  Since we have 2048 items instead of 2047, our Dictionary can require 12 probes in the worst-case; the expected number of probes remains 11 (it's actually 11 and some small fraction).  Either 11 or 12 is an acceptable answer.
    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?
      The number of probes for an unsuccessful search is a where a = n/m is the load factor.  In this case m should be half of n or 1024 for the table size.
    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.
      The actual data stored in the Dictionary takes the same space for both data structures.  The difference is in the extra pointers needed by the hashtable.  For the hashtable, we need one pointer for each Dictionary entry plus one pointer for each list in the hashtable array.  Thus the hashtable requires 2048+1024=3072 extra words.

     

  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
      The time using a sorted array is O(1+ i).  We simply start at the first entry in the array and walk through the items in order until we reach one that is larger than a.  Note that a time of O(i) is not quite correct because i can be zero while the running time can never be zero.
    2. Hashtable
      A hashtable is a poor data structure for this problem.  Because the hashtable contains no ordering information, the best you can do is to search the entire hashtable.  Thus the time is O(n+i).  This can be rewritten as O(n) since the number reported will always be less than the number in the data set.

     

  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
      Two points.  We need one point to determine the translation (i.e., to choose an origin) and another point to determine the scale (we scale the pattern so that both the pattern-point and the scene-point are the same distance from the origin).  Note that for some point choices, the second pattern-point and second scene-point won't be at the same angle; such choices can be rejected quickly without having to test all the other points.
    2. 2-dimensions, translation, rotation, and scaling
      Two points.  We need one point to determine the translation (i.e., to choose an origin).  The other point is used to (1) determine a direction for the X-axis and (2) to determine the scale.
    3. 3-dimensions, translation and scaling
      Two points.  We need one point to determine the translation (i.e., to choose an origin).  The other point is used to determine the scale.
    4. 3-dimensions, translation, rotation, and scaling
      Three points.  One determines the origin, the second determines the direction of the X-axis and the scale, and the third determines the plane of the Y-axis.