Fundamentals of Computer Engineering Homework 3

EECE7205: Fundamentals of Computer Engineering
Homework 3
Problem 1 (30 Points)
Assume we have a hash table with m = 11 slots, and suppose nonnegative integer key values are
hashed into the table using the following hash function h1():
int h1(int key) {
int x = (key + 5) * (key + 5);
x = x / 16;
x = x + key;
x = x % 11;
return x;
}
The sequence of 12 integer key values listed in the left table below are to be inserted in the hash table,
in the order given. Suppose that collisions are resolved by using linear probing.
- On the left table below, show the probe sequence (the sequence of slots to be probed until an
empty one, if any, is available) for each key.
- On the right table below, show the final contents of the hash table after the insertion process is
complete.
No programming code is required for this problem.
Key
Value Probe Sequence Final Hash Table
Contents
43 0
23 1
1 2
0 3
15 4
31 5
4 6
7 7
11 8
3 9
5 10
9
EECE7205 – Homework 3
3 / 3
Problem 2 (40 Points)
Write a C++ program to study how the hash table size affects the collision rate. The following are the
requirements of this program:
a. Generate 1000 random integers that represent the birthdays of people who were born between
January 1, 2000 and December 31, 2004 in the format mmddyy (only five digits if mm is less than 10). An
example of such integers is 112303 for someone who was born on November 23, 2003. For simplicity,
assume that all people were born before the 28th day of their birth month and do not worry about
duplicate birthdays.
b. Define three hash tables with the following sizes: m1 = 97, m2 = 98, and m3 = 100.
c. Simulate storing the 1000 random birthdays that you generate in step a in each of the three hash tables
using hash function h(k) = k mod mi. Where k is the birthday integer and mi is the size of table i (i = 1, 2,
3). Assume that collision is resolved by chaining. You do not need to generate the actual chains in your
program. Instead store in each slot of the table, the number of birthdays values that are mapped to that
slot. Note that, at the end, if a slot of the table has the value x, this means there was (x-1) collisions on
that slot.
d. For each one of the three tables, calculate the minimum, maximum, mean, and variance of the collision
values stored in the table from step c.
e. Comments on the results you calculated in step d by explaining how the hash table size affects the
collision rate.
Problem 3 (30 Points)
If the root of a complete tree starts at index 1 and given the index i of a node, prove mathematically
that the formulas used in the following functions are correct and they will return the indices of that
node’s parent, left child, and right child.