Question

2. (40 pts) Let A, B, and C be three strings each n characters long. We want to compute the longest subsequence that is common to all three strings. (a) Let us first consider the following greedy algorithm for this problem. Find the longest common subsequence between any pair of strings, namely, LCS(A, B) LCS(B, C), LCS(A, C). Then, find the longest common subsequence between this LCS and the 3rd string. That is, supposing that the longest common pair wise subsequence is between A and B, then we return LCS(LCS(A, B), C). Prove or disprove the correctness of this algorithm (b) Design a dynamic programming algorithm for the problem. Derive the dy- namic programming recurrence, clearly explain what each term stands for, and justify the correctness of the recurrence. Explain how you design an efficient algorithm using this recurrence, and analyze its time complexity

Answer 1

a) This will correct solution because atleast LCS of 3 strings will be obtained by applying for any 2 also, and

    then we can apply LCS for third and this string, to get for LCS of all three. This Proves that whatever

    Order of applying LCS to any of three strings first and LCS to the third next will give the correct soluttion

b)

The idea is to take a 3D array to store the 
length of common subsequence in all 3 given 
sequences i. e., L[m + 1][n + 1][o + 1]

1- If any of the string is empty then there
   is no common subsequence at all then
           L[i][j][k] = 0

2- If the characters of all sequences match
   (or X[i] == Y[j] ==Z[k]) then
        L[i][j][k] = 1 + L[i-1][j-1][k-1]

3- If the characters of both sequences do 
   not match (or X[i] != Y[j] || X[i] != Z[k] 
   || Y[j] !=Z[k]) then
        L[i][j][k] = max(L[i-1][j][k], 
                         L[i][j-1][k], 
                         L[i][j][k-1])