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.

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

(A) 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.

(B) Use the results from previous set to estimate the probabilisty of a false positive. I.e, some l cells i_1, i_2, ..., i_l are simultaneously set to TRUE.

YOU CAN EXPLAIN IT ON PAPER, IF YOU DO NOT KNOW THE ANSWER PLEASE DO NOT POST AN INCORRECT SOLUTION