You have decided to get away from it all and live on a lighthouse on an island. No internet,
no cellular phone, no communication with the outside world except for a telephone. The
problem is that the telephone on the lighthouse keeps going out (the sharks keep biting the
wires). Every month, a supply ship will drop off everything you need if you can find a way
to let the people on shore know what you need.
Since the telephone is unreliable, and you would starve if you didn’t alert the shop keeper on
the mainland what you needed, you have to devise your own solution. Luckily, you live in a
lighthouse and you naturally have lots of lights. You devise a system using n lights on a wire
to act as a hash table, T . Alas the problems… this ”hash table”, T , can only indicate 0 or 1
for every index i (i.e. T[i] = 0 if the ith light is off, T[i] = 1 if the ith light is on). You and
the local shop keeper on the mainland agree upon a hash function h that both of you will
use.
Here is how you use your hash function to let the shop keeper know what you want. Everytime
you realize you need something, you request(k) by turning on the h(k)th light. You can do
this in constant time (since the island that the lighthouse is on is very small).
On the mainland, just before he leaves to drop off food and other supplies. The local
shop keeper goes through his supplies and checks to see if you need an item he has. He
asked for(k) which checks if item k was requested by you. This clearly takes constant time
since all he has to do is take out his binoculars and look at the island to see if the h(k)th
light is on.
Questions one:
1) What is the probability the shop keeper sends you something you didn’t
want? i.e. You didn’t compute h(k) and then turn on the h(k)th light. Instead, you
turned on a light because you wanted k′ and it just so happens that h(k′) = h(k). Explain your answer.
2) If you and the shop keeper decided upon two hash functions, h and h′, could
you decrease the probability you were sent things you didn’t ask for if you used both hash
functions? (You do not add any extra lights – all you have are the n light you started with
on a wire.) For your new system, what is the probability that asked for(k) returns
the wrong answer? Explain your answer.
0 comments