University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 477/677 Assignment 4

Due date: Tuesday, March 20, 2012, 2:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or the teaching assistant on or before the due date (except for those problems you are not supposed to turn in).
  1. A three dimensional array A is stored in RAM in column major order. The first index of A is an integer in the range 1 to 8, the second index of A is an integer in the range 5 to 20, and the third index of A is an integer in the range -4 to 7. (Yes, it is possible to declare an array with such bounds in some computer languages.) Assume that each item stored in A takes 2 address locations in RAM, and that the base address of A is 1024. Find the address of A[5,12,3] in RAM.
  2. Build a cuckoo hash table of size 13, using these inputs. The first line is 13, the size of the hash table. Each subsequent line consists of a name, the first hash value of that name, and then the second hash value of that name. Insert the names into the hash table in alphabetical order, which is the order given.
  3. There are a number of versions of cuckoo hashing. The version we learned in class is probably the simplest, where there are two hash functions, and thus only two places where any given item could be stored in the table.
    One problem with cuckoo hashing is that the insertion procedure can enter an infinite loop, and thus the new item cannot be inserted, even though there are still empty places in the table. If the table is mostly empty, this is very unlikely if the hash functions are "good." For example, the probability that we will fail to insert the third item in a table of size m is is 4*m-2*(m-1)-2, which is very small if m is large.
    On the other hand, if we continue to insert items, the insertion procedure will fail with a very high probability before the table is completely full.
    Is a cuckoo hash table that is 70 percent full considered safe, in the sense that it is extremely likely that we can insert another item? If not 70 percent, what is the approximate number of items we can safely (well, almost safely) insert into a cuckoo hash table of size n?
    Hint 1: Look at the world wide web.
    Hint 2: Write a program.
  4. You are running a small business, in which you store information about your customers in a hash table of size 1000. You resolve collisions by using a linked list at each hash table position.
    Assume that your hash function is a good one. If you have 2000 customers, approximately how many positions in your table will have no customers?

Back to Course Page