Question $1.(15$ points$)$

For the min radix priority search tree $($RPST$)$ with range $[0,32),$

$($a$)[8$ points$]$ Perform insert operation into an initially empty RPST in sequence with the following keys: $(7,3),(9,17),(5,5),(19,2),(8,1),(23,7).$ Show each

step. The elements $x$ and $y$ of a key $(x,y)$ stand for the search and priority key values, respectively.

$($b$)[7$ points$]$ Delete $(7,3)$ from the result RPST of part $($a$).$

Question $2.(10$ points$)$ Insert elements with keys $65,2,91,$ and $72$ one at a time into the order$-5$ B$-$tree of the following figure. Show the new tree

after each element is inserted. Do the insertion using the insertion process described in class.

Question $3.[15$ points$]$ Draw a suffix tree for multiple strings. S$1$:acac S$2$: bacb S$3$:acca

Question $4.(10$ points$)$

Suppose that you are to design a Bloom filter with minimum P$($u$)$ with: $n=100,000,m=5000,$ and $u=1000.$

$($a$)(5)$ Using the approach taught in class; compute the number h$,$ of hash functions to use. Show your computations.

$($b$)(5)$ What is the probability, $P(u),$ of a filter error when $h$ has this value?