Q$5.(36$ pts$)$ Given the following Boolean matrix M for S$1,$S$2,$S$3,$S$4,$

a$.(12$ pts$)$ please compute the signature matrix for S$1-$S$4,$ using following

permutations: $[1].$ A$,$E$,$B$,$G$,$F$,$C$,$D

$[2].$ E$,$B$,$C$,$F$,$G$,$A$,$D

$[3].$ D$,$B$,$F$,$G$,$A$,$E$,$C

b$.(12$ pts$)$ Please compute the pairwise Jaccard similarity of S$1-$S$4$ using

$(1)$ the original representation in M; $(2)$ Minhashing generated by the

permutations in question $($a$)$

c$.(12$ pts$)$ Consider the S$1$ and S$2$ only. When using two hashing functions:

$7$ and g$($x$)=(2$x$+3)$mod$,7,$ what are the signatures of S$1$ and S$2$ after hashing?