Slide $11$ of Lecture $20$:

Solution $1.$ Dynamic programming.

Def. OPT$(i,j)=$ length of LCS of prefix strings $x_1{x}_{2}dots{x}_i$ and $y_1{y}_{2}dots{y}_j.$

Goal. OPT$(m,n).$

Case $1.x_i=y_j.$

$1+$ length of LCS of $x_1{x}_{2}dots{x}_{i-1}$ and $y_1{y}_{2}dots{y}_{j-1}.$

Case $2.x_i{y}_j.$

Delete $x_i$ : length of LCS of $x_1{x}_{2}dots{x}_{i-1}$ and $y_1{y}_{2}dots{y}_j.$

Delete $y_j$ : length of LCS of $x_1{x}_{2}dots{x}_i$ and $y_1{y}_{2}dots{y}_{j-1}.$

Bellman equation.

OPT$(i,j)=\{\begin{array}{ccc}0& ifi=0or& j=0\\ 1+\text{O}\text{P}\text{T}& (i-1,j-1)if& x_i=y_j\\ \text{m}\text{a}\text{x}& \{OPT(i-1,j),\text{O}\text{P}\text{T}(i,j-1)\}if& x_i{y}_j\end{array}$

Slide $13$ of Lecture $19$:

Example

$\backslash$table$[[,,s,a,b$

$1.$ Given a digraph G $=($V$,$ E$),$ its transitive closure G$$ is a digraph defined as follows: It has the same vertex set V as G and contains an edge from a vertex a to another vertex b if and only if there is a directed path from a to b in G$.$ Suppose we want to design a DP algorithm that outputs G$$ on input G$.$ Design the subinstances and the Bellman Equation. $($Note that though this is not an optimization problem, DP is still helpful.$)$

$2.$ Compute the shortest path from vertex $2$ to every other vertex of the attached graph using the Bellman$-$Ford Algorithm. Show your work by constructing the table as in Slide $13$ of Lecture $19.$

$3.$ Compute the length of longest common subsequence for the two input strings x $=$ ABCBDAB and y $=$ BDCABA using the dynamic programming algorithm on Slide $11$ of Lecture $20.$ Show your work by filling the DP table.