Chapter 8, Problem 16SE

In Exercises 15-18 we develop a dynamic programming algorithm for finding a longest common subsequence of two sequences $a_1,a_2,\mathrm{....},a_m$ and $b_1,b_2,\mathrm{....},b_n$, an important problem in the comparison of DNA of different organisms.

Let L(i,j) denote the length of a longest common subsequence of $a_1,a_2,\mathrm{....},a_m$ , and $b_1,b_2,\mathrm{....},b_n$ , where $0\le i\le m$ and $0\le j\le n$ . Use parts (a) and (b) of

Exercise 15 to show that L(I,J) satisfies the recurrence relation $L\left(i,j\right)=L\left(i-1,j-1\right)$ if both i and j are nonzero and $a_i=b_j$ , and $L\left(i,j\right)=\max \left(L\left(i,j-1\right),L\left(i-1,j\right)\right)$ if both i and j are nonzero and $a_i\ne b_j$ ,and the initial condition $L\left(i,j\right)=0$ if $i=0$ or $j=0$ .