P$1($LCS$)(10$ pts$)$ Find the Longest Common Subsequence.

$(3$ pts$)$ Fill in the table. Be careful: one mistake in one cell can cause the remaining cells to be wrong. $(3$pts$)$ Record the direction as well using the symbols: $""$ for diagonal, $"-"$ for left, $"|"$ for up$.$ E$.$g$."0-"$ in a cell means the value is $0$ and the arrow is left.

Use the LCS$\_$length $(x,Y)$ pseudocode from the slides. Whenever there is a tie between left and up$,$ chose up $($this is consistent with LCS$\_$length $(x,Y)).$ Penalty for the wrong choice in case of a tie: $1$ pt$.$

X$=$T R A Y

Y$=$ S T O R M

$(2$ pts$)$ LCS final answer: Length: Subsequence:

$(2$pt$)$ Highlight the cells that you visit when recovering the longest common subsequence.

PSEUDOCODE:

$LC{S}_l$ength $(x,Y)$

$N=$ length $(x)$

$P=$ length $(Y)$

$b=2D$ array $ofN+1$ rows, $P+1$ columns

$C=2D$ array $ofN+1$ rows, $P+1$ columns

for $i=0toN$

$c[i,0]=0$

for $j=0toP$

$c[0,j]=0$

for $i=1toN$

for $j=1toP$

$if{x}_{i-1}==y_{j-1}$

$c[i,j]=c[i-1,j-1]+1$

$b[i,j]=1\frac{,}{\frac{?}{?}}$ diagonal

else $ifc[i-1,j]z_C[i,j-1]$

$c[i,j]=c[i-1,j]$

$b[i,j]={?}^{{?}^{?}}\frac{\frac{?}{?}}{u}p$ arrow

else

$c[i,j]=c[i,j-1]$

eft arrow