CSE 326 - Autumn 2000

Homework #4
Due: Friday Oct 27th

1.  Weiss 5.1.  Note that if you want to receive partial credit for an
    "close but not entirely correct" answer, you must show the
    intermediate states as well.  Typing up this assignment and using
    "cut and paste" in your word processor will make it much easier!

2.  Weiss 5.10.  Assume a pointer is 4 bytes long, and that the hash
    table is an array of pointers to words.  State the load factor
    that you using (choose a value that is good for quadratic
    probing).  Give your answer in bytes.

3.  Weiss 5.11.  Assume that a bool takes up only one bit, and that the
    table of bools is packed as densely as possible (8 bools to the
    byte).

    Fun fact: this is how the "spell" command on Unix is actually
    implemented!

BONUS POINT QUESTION:

4.  Consider the situation where you decide to use a really huge
    hashtable (e.g. a gigabyte in size), which may be allocated
    explicitly on disk or in virtual memory that is mostly
    non-resident in RAM.  Furthermore, your application is such that
    you may frequently need to completely erase the hashtable and
    start over again.  In such a situation you want to minimize the
    cost of initializing the empty hashtable.

    Ordinarily it would require O(tablesize) time to simply go through
    the hashtable at the beginning and set all the entries to NULL
    and/or set all the entry "status" bits to "empty".  Your task is to
    devise a scheme that allows you avoid explicitly initializing the
    hashtable.  Under the assumption that the operating system can
    return an uninitialized block of memory of any size in constant
    time, you only have to do a constant amount of further work O(1)
    before you begin using the hash table.  Furthermore, your scheme
    should allow you to erase all the contents of the hashtable and
    start over again also in O(1) time.

    You may not make any assumptions about the contents of
    uninitialized blocks of memory (in particular, they do not only
    contain 0's!).  Your scheme may involve allocating one or more
    additional large arrays: if so, be sure to state how large they
    should be (in absolute terms, or in terms of the tablesize and/or
    the maximum load factor), and take care to avoid spending more
    than constant time in initializing them.  Although the tablesize
    is large, the range of keys is much larger; do not attempt to
    allocate an array as large as the entire range of keys.

    Carefully describe the data structures needed to implement your
    scheme, and provide an English description of how it works.