Reading

These notes.

Quiz questions

Review quiz problems

Memoized LCS and the Table

Recall the memoized version of LCS (here in C++ syntax):
int LLCS(string &X, int m, string &Y, int n, int **T, int **E)
{
  if (T[m][n] == -1)
  {
    if (m == 0 || n == 0)
      T[m][n] = 0;
    
    else if (X[m-1] == Y[n-1])
    {
      E[m][n] = 1;
      T[m][n] = 1 + LCS(X,m-1,Y,n-1,T);
    }
    else
    {
      int t1 = LCS(X,m-1,Y,n,T);
      int t2 = LCS(X,m,Y,n-1,T)
      E[m][n] = t1 >= t2 ? 2 : 3;
      T[m][n] = max(t1,t2);
    }    
  }
  return T[m][n];
}
      
Break up into groups and run through how LCS works on input X := dine and Y := tied. Specifically, keep your eye on table T, and pay attention to the order in which LCS fills the table T.

When you're done, use the table E to recover the LCS.

Dynamic Programming and LCS

If you paid attention to the memoized LCS algorithm, you should have noticed that the recursive structure of LCS ensures that we don't fill table entry T[i][j] until either T[i-1][j-1] is filled in (in the case where X[i-1] = Y[j-1]) or both T[i-1][j] and T[i][j-1] are filled in.

What if we shifted our perspective, and made filling in the table T (and, ultimately, E as well) our goal. Could we dispense with the top-down recursive control of the LCS() from above and just fill in the table with some nested loops?

Let's try it using dine and tied again and see how it might work. (We did this in class.)

So the moral of the story is that we can, but we have to be careful! In the memoized version, the recursive control ensured that we never filled in a table entry before the entries it relied on were already filled in. Now it's up to us to carefully fill in the table in an order that ensures the same thing.

  //-- Fill in tables T and E --//
  for(int i = 0; i <= m; i++)
    T[i][0] = 0;
  for(int j = 0; j <= n; j++)
    T[0][j] = 0;
  for(int i = 1; i <= m; i++)
    for(int j = 1; j <= n; j++)
      if (X[i-1] == Y[j-1])
      {
	T[i][j] = 1 + T[i-1][j-1];
	E[i][j] = 1;
      }
      else
      {
	int t1 = T[i-1][j];
	int t2 = T[i][j-1];
	if (t1 >= t2) { T[i][j] = t1; E[i][j] = 2; }
	else          { T[i][j] = t2; E[i][j] = 3; }
      }
      

The algorithm we get this way is an example of what is called "dynamic programming". Check out lcsdynamicprog.cpp for a full implemention.