Problem $1.$ LCS $(5$ points$)$

This problem refers to the DP algorithm we covered in class to find a Longest Common Subse$-$

quence.

$($a$)$ What is the length of the LCS for the sequences $x=($:$N,E,N,T,H,O$:$),Y=($:$E,N,O,E,N,H$:$)?$

What is its value?

Solution:

$($b$)$ Write the pseudocode for an algorithm like PRINT$-$LCS$,$ but one that doesn't use the $b$

table. Instead, your algorithm should use the $c$ table and sequences $x=$ and

$Y=($it can also have additional parameters if you need them$).$

Solution: