Problem $1.(30$ points$)$

a$.$ Construct a heap for the list $2,15,12,10,6,14,8$ by the bottom$-$up algorithm. $(10$ p$.)$

b$.$ Construct a heap for the list $2,15,12,10,6,14,8$ by successive key insertions $($top$-$down algorithm$).(10$ p$.)$

c$.$ Is it always true that the bottom$-$up and top$-$downfalgorithms yield the same heap for the same input? $(10$ p$.)$

Problem $2.(40$ points$)$

Consider the problem of searching for genes in DNA sequences using Horspool's algorithm. A DNA sequence consists of a text on the alphabet $\{A,C,G,T\}$ and the gene or gene segment is the pattern.

a$.$ Construct the shift table for the following gene segment of your chromosome $10$: $(20$ p$.)$

TCCTATTCTTT

b$.$ Apply Horspool's algorithm to locate the above pattern in the following DNA sequence: $(20$ p$.)$

TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTTT

Problem $3.(30$ points$)$

For the input $63,42,45,64,53,41$ and hash function $(K)=$Kmod$11$

a$.$ Construct the open hash table. Find the largest number of key comparisons in a successful search in this table. $(15$ p$)$

b$.$ Construct the closed hash table. Find the largest number of key comparisons in a successful search in this table. $(15$ p$.)$