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

CSC 477/677 Assignment 7
Due date: Thursday, April 24, 2008, 4:00 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 on or before the due date.
-
A hash table has size 1000, and 2000 items are placed in the table.
Let one of those items be called "Bob."
Assuming that each hash index is independently chosen at random,
what is the expected number of items (including Bob) that will be
placed in the same place as Bob?
-
Refer to Open addressing, Section 11.4 of your textbook.
Suppose U(k,i) = (h'(k) + 1 + 2 + ... + i) mod m.
-
Is this a disguised form of quadratic probing?
-
Show that if m is a power of 2, the probe sequence covers the entire
hash table, but if m is not a power of 2, it does not.
-
Work Exercise 27.2-3 on page 712 of your textbook.
-
Does there exist a sorting network of size 7 that sorts sequences
of length 5? Either find one, or prove that none exists, or find a
reference on the world-wide-web stating that none exists.

Back to
Course Page