The class random$\_$generator has been updated $($random$\_$generator.h and ran$-$

dom$\_$generator.cc$)$ by a member function which generates random strings of a fixed

length using the a given number of characters from the alphabet, starting with $"$a$".$

char$*$ random$\_$string$\_$m$($int $n,$ int no$\_$ch$)$

The function allocates $n+1$ characters. The first $n$ characters $(0$dotsn$-1)$

are chosen at random using the first no$\_$ch characters from the alphabet start$-$

ing with $"$a$"($e$.$g$.,$ for no$\_$ch $=4$ the characters are randomly chosen out of

$\{a,b,c,d\}.$ The $n-$th character is set to $0$ in order to mark the end

of the string.

Dynamic programming $(70$ points$)$

The dynamic programming Smith$-$Waterman algorithm is matching sequences recur$-$

sively defined as follows, given $x=x_1,$dots,$x_n($along table rows$)$ and $Y=y_1,$dots,$y_m$

$($along table columns$).$

$M(i,0)=0,$ for all $0in$

$M(0,j)=0,$ for all $0jm$

$M(i,j)=$max$\{\begin{array}{ccc}M(i-1,& j-1)+2if& x_i=y_j\end{array}$

$M(i-1,j-1)-1if{x}_i{y}_j$

$M(i-1,j)-1if-is$ inserted into $Y$

$M(i,j-1)-1if-is$ inserted into $x$

The function $M(i,j)$ defines a so called matching score for the partial sequences $x_i$

and $Y_j.$ If in the recursive definition of $M$ the maximum value is due to the third

or fourth line, you have to insert the character $"-"$ into either $x$ or $Y$ in order to

reconstruct the matching sequences $x^{\text{'}}$ and $Y^{\text{'}}.$ Similar to the LCS problem we need

only need a table to store the $M(i,j)$ values, but an additional table that allows us

to later generate $x^{\text{'}}$ and $Y^{\text{'}}$ from $x$ and $Y.$