From jacobson@math-cs.cns.uni.edu Mon Nov 13 20:42:34 2006
Date: Mon, 13 Nov 2006 14:42:30 -0600 (CST)
From: Mark Jacobson <jacobson@math-cs.cns.uni.edu>
To: 810-080-02-FALL@uni.edu
Subject: [810-080-02-FALL] Hashing assignment due Wednesday...

Hi 080 students,

      Here is the assignment that is due on Wednesday, in case you missed
class today.

      The hash function is:

          h(IDnumber) = (IDnumber MOD 29) + 1

          h(x) = (x mod 29) + 1

      so the home addresses go from 1 to 29 in the hash table,
         instead of going from 0 to 28.

       http://www.cns.uni.edu/~jacobson/hashTables.html

          has a link to

       5.  October 2000 Hashing example, which links to URL:

           http://www.cns.uni.edu/~jacobson/hashingOct2000.txt

-----------------------------------------------------------------------
    SHOW YOUR WORK.                             DUE WEDNESDAY 11/15/2006
    DRAW THE TABLE - IT HAS 29 LOCATIONS, from 1 to 29.

The hashing function is ((ID MOD 29) + 1)
The 6 digit ID numbers might be UNI ID numbers.

1. Calculate the successful search average
    performance for the table.

2. Calculate the unsuccessful average search
    performance for the table.

    SHOW YOUR WORK.
    DRAW THE TABLE - IT HAS 29 LOCATIONS, from 1 to 29.
    SHOW YOUR WORK.                             DUE WEDNESDAY 11/15/2006
--------------------------------------------------------------------
    Do not have to redo what we did in class, i.e. the
    hash table with 17 locations is already done.

    http://www.cns.uni.edu/~jacobson/c080.html

    Study the links to Hash Tables for many, many examples of
    how to calculate successful and unsuccessful search performance.

    Know the terms and concepts behind them for:

       load factor
       collision resolution
       collision resolution strategy of linear probing
       treating an array or hash table file as circular
       home address
       collision
       probes (of memory or for files it would be disk accesses)
       average successful search performance
       average unsuccessful search performance

       Think about space/time tradeoffs.

       A load factor of only 0.2 would probably mean a very, very good
       average successful search performance value, perhaps very close
       to 1.0, if not a perfect 1.0.  80% of the slots are empty.

       But the cost in terms of MEMORY, i.e. SPACE would be that it
       used 5 times the amount of memory needed to just store the
       items.

       Suppose the load factor is 0.9 and there is very little wasted
       SPACE.  Only 10 percent of the slots are empty.

       What is the cost here????  Time to look up information.  The
       average successful search performance would be quite high in
       terms of number of probes of the table to find something.
       The program would be slower in its searches.

Mark