Consider the Bloom filter discussed in Section 20.3. Define k = number of hash functions;

N = number of bits in hash table; and D = number of words in dictionary.

a. Show that the expected number of bits in the hash table that are equal to zero is expressed as

b. Show that the probability that an input word, not in the dictionary, will be falsely accepted as being in the dictionary is

c. Show that the preceding expression can be approximated as

4 || 1 k_N D