PLEASE CLEARLY AND CORRECTLY ANSWER THIS QUESTION WITH DETAILED EXPLANATIONS. IF YOU REALLY DO NOT KNOW THE ANSWER PLEASE DO NOT ANSWER THIS QUESTION. IF YOU WRITE ON PAPER AND DOWNLOAD HERE THIS WILL BE MUCH MORE USEFUL.TY.

A bloom filter is a fast set data structure that maintains a set S of keys. One can insert keys into the set and test whether a given key k belongs to the set. It may used in applications where the keys are "complicated" objects such as TCP packets or images that are expensive to compare with each other.

The data structure is an array T of Booleans size m with l different hash functions h1, ..., hl Initially, `T[i] = FALSE` for all `i`.

If a key k is to be inserted we first compute i_1 = h_1(k), \ldots, i_l = h_l(k) and then we set T[i_1] = ... T[i_l] = TRUE

Note: A bloom filter is *not* a hash table, but they both use hash functions in interesting ways.

A)Suppose we wish to find out if an element k is a member of the set by checking if T[h_1(k)], ..., T[h_l(k)] are all true. Explain whether this can lead to a *false positive* i.e, the approach wrongly concludes that k belongs to the set when it was never inserted; or *false negative* i.e, the approach wrongly concludes that k does not belong to the set when it does.

B) Suppose our hash functions are guaranteed to be uniform. I.e, for any randomly chosen key k, for any hash function h_i and cell j, P( h_i(k) = j) = 1/m If n keys are chosen at random and inserted into the filter, compute that probability that any given cell T[j] is set to FALSE after this.