Problem $1$

Fill in the graph below using the optimal longest common subsequence alignment of strings ABBD and ADB. Recall that the cost for matching two symbols is equal to $0,$ the cost for deleting or inserting a symbol is equal to $1,$ and the substitution is

not considered.

a$)$ Fill in the graph$-$looking dynamic programming matrix to the left with the optimal alignment costs and the graph$-$

looking matrix to the right with the corresponding link information. When done, use backtracking to extract all

possible alignments of the two strings. In case of a tie, process a DIAGONAL move first followed by a VERTICAL

move and then a HORIZONTAL move.