A subsequence of a given sequence is just the given sequence with some elements

$($possibly none$)$ left out. Formally, given a sequence $s=s_1{s}_{2}dots{s}_n,$ we say

another sequence $r=r_{1}dots{r}_k$ is a subsequence of $s$ if there is a strictly increasing

sequence $i_1,i_2,$dots,$i_k$ of indices such that for all $j=1$dotsk we have $r_j=s_{i_j}.$

Given two sequences $x=x_{1}dots{x}_n$ and $y=y_{1}dots{y}_m,$ let $lcs(x,y)$ denote the

maximal length of any sequence that is a subsequence of both $x$ and $y.$

$($a$)$ Derive a suitable recurrence for $lcs(x_1,$dots,$x_k,y_{1}dots{y}_l)$ for $1kn$ and

$1lm.$

$($b$)$ Give a $O(mn)-$time dynamic programming algorithm to compute $lcs(x,y).$

$($c$)$ Prove that your algorithm is correct and runs in $O(mn)-$time.