$(5$ pts$)$ Implement in Python a class to model hash functions from a certain family H of hash functions. $($Call this class HashFamily.$)$ The constructor for H should take n and p as arguments. The constructor should generate a random set of p distinct indices from $\{0,1,...,$ n$-1\}$ and remember this set, call it S$.$ This class should have a method hash$($x$)$ which computes the hash value of any n$-$bit number x as follows. The method first extracts $\{$x$[$i$]$ : i in S$\}.$ It then formulates the p$-$bit number obtained from this set in order of increasing index and returns this p$-$bit number in decimal. $($Added $12-17$: See Q&A On this question at the end of this document.$)$

$(5$ pts$)$ Implement in Python a Bloom Filter $($BF$)$ as a class.

The constructor should take m$,$ k$,$ and n as arguments, where m and k are as done in class and n is the number of bits in an input. $($Its okay to limit m to be a power of $2.)$ The constructor should then create k random hash functions as HashFamily objects with arguments n$=$n and p$=$log$\_2($m$).$ It maintains these hash functions in its state.

Support insert and lookup as done in class.

Support a bash insert method $-$ a wrapper around insert $-$ as a convenience method $($see next question$).$

$(7$ pts$)$ In this question, the aim is to empirically study how various parameter settings impact the false positive rate on simulated data.

Generate $1000064-$bit numbers at random and store this list somewhere. Call it S$.$

for m in $[64,128,256,512,1024,2048,...,65536]$:

for k in $[1,2,4,8,...,$ m$/2]$:

Create a BF with params m$=$m$,$ k$=$k$,$ n$=64.$

for q in $[$m$,2$m$,4$m$,8$m$,16$m$,32$m$,64$m$]$

Generate q n$-$bit numbers and batch insert them all into the BF$.($Note that these are inserted into an existing BF$.)$

Generate $1000$ random n$-$bit numbers from scratch and lookup each of them in the BF$.$ Calculate the proportion of these $1$K numbers on which the BF answers YES. The higher this proportion the higher the false positive rate.

Report your results in a table whose rows correspond to $($m$,$ k$,$ q$)$ one row per triplet.

Analyze your results to draw meaningful conclusions about the impact of the various parameter settings on the false positive rate.

Q: Having difficulty understanding the requirements for problem $1$ of HW$6.$ Ask: explain a bit more with an example or what exactly the class functionality should be$?$

A: h $=$ HashFamily$($n$=6,$p$=2)$ #

After the constructor has executed, h$.$S is a random $2-$element subset of $\{1,2,3,4,5\},$ e$.$g$.$ h$.$S $=\{1,3\}.$

Next, consider h$.$hash$($x$)$ where x is an n$-$bit binary number, represented however you wish $($e$.$g$.$ as bit array$).$ Say x $=011011.$ For h$.$S$=\{1,3\}$ the bits in x that h$.$S touches are in bold next. $011011$ Projecting out these bits forms the binary number $10$ which in decimal is $2.$ So hash.$($x$)$ returns $2.$