Copyright © T. H. Merrett
308-420A Secondary Storage Algorithms and Data Structures Week 7
Assignment 8
Using the hashed telephone book of Assignment 7, write a program which
computes the load factor, alpha, and the probe factor, pi:
alpha= number of records present / capacity;
pi= total probes required to find all records / number of records;
opi, the optimistic value for pi, calculated by assuming that each
record not falling on its home block requires only one extra probe.
Using the Poisson distribution, compute a theoretical approximation to pi
for the alpha that you found, by supposing that each record which overflows from
its home block requires only one extra probe. (You can approximate the infinite
sum by summing only while the summand is large enough.) Compare the measured and
theoretical numbers and explain the difference.
*Shared marks for shared work*: assignments should be your own work; marks
for joint assignments will be divided by the number of collaborators.
But please feel free to work in groups to learn or for extra work that
is not for marks.