Question

Use Exercise 16to construct a dynamic programming algorithm for computing the length of a longest common subsequence of two sequences${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{a}}_{\mathbf{m}}$and ${\mathit{b}}_{\mathbf{1}}\mathbf{,}{\mathit{b}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{b}}_{\mathbf{n}}$, storing the values of$\mathit{L}\left(i,j\right)$as they are found.

Short answer

An algorithm for determining the longest common subsequence of $2$sequences is,

$L\left(i,j\right)=\max \left\{L\left(i,j-1\right),\left(i-1,j\right)\right\}$

Step-by-step solution

Given information

We have given that,

The $2$sequences are, $a_1,a_2,....,a_m$and$b_1,b_2,....,b_n$ .

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

${\mathit{F}}_{\mathbf{n}}\mathbf{=}{\mathit{F}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{+}{\mathit{F}}_{\mathbf{n}\mathbf{-}\mathbf{2}}$

With base values $\mathit{F}\mathit{O}\mathbf{}\mathbf{=}\mathbf{}\mathbf{0}$and ${\mathit{F}}_{\mathbf{1}}$is equal to$\mathbf{1}$ .

Calculation

We can use dynamic programming to create an algorithm for calculating the length of a common subsequence of two sequences

$a_1,a_2,....,a_m$and $b_1,b_2,....,b_n$

As shown below.

Procedure longest subsequence is,

$\left(a_1,a_2,....,a_m,b_1,b_2,....,b_n\right)$

For $i=1 \mathrm{to} m$

$L\left(i,0\right)=0$

For,

$j=1 to n$

$L\left(0,j\right)=0$

For

$i=1 to m$

And

$j=1 to n$

If $a_i=b_j$

Then

$L\left(i,j\right)=L\left(i-1,j-1\right)+1$

Else

$L\left(i,j\right)=\max \left\{L\left(i,j-1\right),L\left(i-1,j\right)\right\}$

Return

Thus, an algorithm for determining a longest common subsequence of two sequences is,

$L\left(i,j\right)=\max \left\{L\left(i,j-1\right),\left(i-1,j\right)\right\}$