Question

Develop an algorithm for finding a longest common subsequence of two sequence ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{a}}_{\mathbf{m}}$and ${\mathit{b}}_{\mathbf{1}}\mathbf{,}{\mathit{b}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{b}}_{\mathbf{n}}$using the values $\mathit{L}\left(i,j\right)$found by the algorithm in Exercise $\mathbf{17}$.

Short answer

The procedure$\mathrm{lcsub}\left(a_1,a_2....,a_m:\mathrm{sequencewith}m\ge 1;b_1,b_2,...b_n:\mathrm{sequencewith}n\ge 1\right)$

$l=\mathrm{lengthlcsum}\left(m,n\right)$

If $a_m=b_n$then

$c_l=a_m$

$c_1{c}_2.....c_{l-1}=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{n-1}\right)$

If $a_m\ne b_n$then

$c=\mathrm{lcsub}\left(a_{1,}{a}_2,...,a_{m-1};b_1,b_2,...,b_n\right)$

$d=\mathrm{lcsub}\left(a_{1,}{a}_2,...,a_m;b_1,b_2,...,b_{n-1}\right)$

If$c>d$then

$c_1{c}_2.....c_l=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{n-1}\right)$

Else

$c_1{c}_2.....c_l=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{m-1}\right)$

Return$c_1{c}_2....c_l$

Step-by-step solution

Given information

We have given that,

The values $L(i,j)$found by the algorithm in Exercise$17$ .

Definition and formula to be used

In mathematics, the term "dynamic programming" refers to the process of breaking down a decision into a series of decision steps over time in order to simplify it, this is accomplished by creating a series of value functions ${\mathit{V}}_{\mathbf{1}}\mathbf{,}{\mathit{V}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{V}}_{\mathbf{n}}\mathbf{,}$each of which takes y as an argument and represents the state of the system at time $\mathit{i}$from $\mathbf{1}$to $\mathit{n}$.

We will use the formula of Dynamic programming algorithm

$F_n=F_{n-1}+F_{n-2}$

With base values $FO=0$and $F_1$is equal to$1$ .

Calculation

From the previous exercise$17$ , we will use the algorithm to compute all lengths$L(i,j)$ which is necessary in this algorithm.

So, The algorithm "$\mathrm{lcsub}$" and the input are $2$sequences$a_1,a_2,...a_m$ and$b_1,b_2,...b_n$ .

procedure$\mathrm{lcsub}\left(a_1,a_2....,a_m:\mathrm{sequencewith}m\ge 1;b_1,b_2,...b_n:\mathrm{sequencewith}n\ge 1\right)$

Now, we compute the length of the longest common subsequence,

So, the number of elements is,

$l:=\mathrm{lengthlcsum}\left(m,n\right)$

Solve the length of longest common subsequence

Now, we will solve the length of the longest common subsequence is,

If $a_m=b_n$, then the last common element is,

$a_m=b_n$

Then, we will determine the remaining $l-1$elements $\left(\mathrm{byexercise}15\right)$.

If $a_m=b_n$then

$c_l=a_m$

So,

$c_1{c}_2.....c_{l-1}=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{n-1}\right)$

Now,

If $a_m\ne b_n$then

$L\left(m,n\right)=\max \left\{L\left(m-1,n\right),L\left(m,n-1\right)\right\}$

If $L\left(m-1,n\right)>L\left(m,n-1\right)$, then the longest common subsequence has to be the longest common subsequence of $a_1,a_2,...a_{m-1}$and $b_1,b_2,...b_n$.

If $L\left(m-1,n\right)\le L\left(m,n-1\right)$, then the longest common subsequence has to be the longest common subsequence of $a_1,a_2,...a_m$and $b_1,b_2,...b_{n-1}$.

Now,

If $a_m\ne b_n$then

$c=\mathrm{lcsub}\left(a_{1,}{a}_2,...,a_{m-1};b_1,b_2,...,b_n\right)$and $d$is equal to $\mathrm{lcsub}\left(a_{1,}{a}_2,...,a_m;b_1,b_2,...,b_{n-1}\right)$.

If $c>d$then $c_1{c}_2.....c_l=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{n-1}\right)$else $c_1{c}_2.....c_l$ is equal to $\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{m-1}\right)$

So, finally we will return the longest common subsequence of the all above given sequences.

So,

Return $c_1{c}_2....c_l$

Thus, the solution of the given condition is,

procedure $\mathrm{lcsub}\left(a_1,a_2....,a_m:\mathrm{sequencewith}m\ge 1;b_1,b_2,...b_n:\mathrm{sequencewith}n\ge 1\right)$

$l=\mathrm{lengthlcsum}\left(m,n\right)$

If $a_m=b_n$then

$c_l=a_m$

$c_1{c}_2.....c_{l-1}=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{n-1}\right)$

If $a_m\ne b_n$then

$c=\mathrm{lcsub}\left(a_{1,}{a}_2,...,a_{m-1};b_1,b_2,...,b_n\right)$

$d=\mathrm{lcsub}\left(a_{1,}{a}_2,...,a_m;b_1,b_2,...,b_{n-1}\right)$

If $c>d$then

$c_1{c}_2.....c_l=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{n-1}\right)$

Else

$c_1{c}_2.....c_l=\mathrm{lcsub}\left(a_1,a_2,...,a_{m-1};b_1,b_2,...,b_{m-1}\right)$

Return\({{c}_{1}}{{c}_{2}}.....{{c}_{l}}\)