Let the hash functions all be of the from h(x)=ax+b mod 16 for some a & b. You should treat the results as a 4 bit binary integer. Determine the tail length for each stream element and the resulting estimate of the number of distinct elements if the hash function is: a) h(x) = 2x+3 mod 16 b) h(x) = 4x+1 mod 16 c) 5x mod 16

S = { 2, 1, 6, 1, 5, 9, 2, 3, 5 } |b| = 2

(a) h(x) = 2x + 3 mod 16

No of distinct elements = $2^max[r(a)] = 2^0 = 1$

(b) h(x) = 4x + 1 mod 16

No of distinct elements = $2^max(r(a))$

$= 2^0 = 1$

( c ) 5x mod 16

No of distinct elements = $2^max(r(a))$

$= 2^1 = 2$