Exercise 11.1-4 Answer

[grasscannoli]

I had come up with a similar solution to the one given here. But there's a problem with this answer - since the huge array is filled with junk values, its is possible that it may actually contain a value that points to an element in S, although at an invalid key position. So when this invalid key is given for search, the data structure will give a satellite value for this key, although it was intended for another key. I get it that the probability of this happening is very low, but nonetheless, this data structure is not fool proof...