Performance and Test, Spring 2008: Episode 3.2

Spring 2008

Description

Schedule

Resources

Exercises, Wednesday, February 20, 11:00—12:00, Room 3A14.

Some of the following exercises will be discussed at the exercise session. The exercised marked [CLRS] are taken from another textbook (by Cormen, Lester, Rivest, and Stein) — you do not need that book to solve the exercises.

1. Discuss with your group partner what is the advantage of cuckoo hashing over hashing with chaining? (hint: summarize complexities of operations and compare them)

2. Let m be the size of a hash table. Show that if |U| > nm, there is asubset of U of size n consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is linear. [Taken from CLRS 11.2-5]

3. Suppose we wish to search a linked list of length n, where each element contains a key k along with a hash value h(k). Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key? [Taken from CLRS 11.3-1]

4. RS 14.42, 14.43, p. 629

In addition, you must hand in a solution to the following problem before Wednesday, Feb 27, at 11:00. You can hand in at the beginning of the lecture Wednesday morning, or at any other time in the course pigeon hole, in front of the study administration.

• Professor Marley hypothesizes that substantial performance gains can be obtained if we modify the separate-chaining scheme so that each list is kept in sorted order. How does the professor's modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions? [Taken from CLRS 11.2-3]

  Hint: the expected length of each chain is the same as before. First, describe the expected (i.e., average) running times in terms of M (the current size of the table) and N (the current number of keys in the table). Second, explain under what assumptions the operations take expected constant time.

Last updated Feb 21, 2008 10:47 Dan Witzner Hansen, Kristian Støvring