Consider the Bloom ?lter discussed in Section 3.3 in your textbook (Token-Based Authentication). De?ne 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 ? = (1? k N )D

(b) Show that the probability that an input word, not in the dictionary, will be falsely accepted as being in the dictionary is P = (1??)k

(c) Show that the preceding expression can be approximated as P ? (1?e?kD/N)k