A linear-hashing scheme with blocks that hold k records uses a threshold constant c, such that the current number of buckets n and the current number of records r are related by r = ckn.

(a) Suppose for convenience that each key occurs exactly its expected number of times. As a function of c, k, and n, how many blocks, including overflow blocks, are needed for the structure?

(b) Keys will not generally distribute equally, but rather the number of records with a given key (or suffix of a key) will be Poisson distributed. That is, if Lambda is the expected number of records with a given key suffix, then the actual number of such records will be i with probability pdf_poisson(i). Under this assumption, calculate the expected number of blocks used, as a function of c, k, and n.