4. Bloom filters. Suppose you are given a Bloom filter of size m with t hash functions (each of which can be assumed to be computed in O(1) time and n inserted elements. Let S be the set representing the keys being stored. (a) (1 point) Assuming simple uniform hashing, what is the expected time (in terms of t) for searching for a key k that may or may not be in S). (b) (3 points) Between using Bloom filters and hashing with chaining, how would you determine which has the better search time if a = n/m is fixed and t is the only variable. (c) Recall that the probability of a false positive is upper bounded by the following value: p= (1 - e-tn/myt (1) (5 points) What is the number of hash functions required to get a false positive rate of at most 0.02 if m= 100 and n = 10? (ii) (7 points) For any given fixed load factor n/m find the number of hash functions that will minimize the false positive rate. (Hint: differentiate p) (d) (4 points) The standard Bloom filters discussed in class do not support deletion oper- ations. Without changing the number m of array slots, describe a way to modify the data structure to allow for deletions and explain how this modification enables deletion to work 4. Bloom filters. Suppose you are given a Bloom filter of size m with t hash functions (each of which can be assumed to be computed in O(1) time and n inserted elements. Let S be the set representing the keys being stored. (a) (1 point) Assuming simple uniform hashing, what is the expected time (in terms of t) for searching for a key k that may or may not be in S). (b) (3 points) Between using Bloom filters and hashing with chaining, how would you determine which has the better search time if a = n/m is fixed and t is the only variable. (c) Recall that the probability of a false positive is upper bounded by the following value: p= (1 - e-tn/myt (1) (5 points) What is the number of hash functions required to get a false positive rate of at most 0.02 if m= 100 and n = 10? (ii) (7 points) For any given fixed load factor n/m find the number of hash functions that will minimize the false positive rate. (Hint: differentiate p) (d) (4 points) The standard Bloom filters discussed in class do not support deletion oper- ations. Without changing the number m of array slots, describe a way to modify the data structure to allow for deletions and explain how this modification enables deletion to work