Class 35: More Memoization and Dynamic Programming


Reading
Sections 15.2 of Introduction to Algorithms.

Homework
Your homework is to define a Scheme function (best-parens i j) that allows you to recover the optimum parenthesization from the table of best k values. To do this and test this, you'll use the code I've already written.
  1. mcm.scm: a module for creating random matrix chain multiplication problems
  2. table.scm: a module for arbitrary dimensional tables
  3. mcm-sol.scm: a module for solving matrix chain mulitiplication problems. Contains the memoized algorithm, augmented to keep track of the optimum k values. The optimum k values are stored in the global table bestK.
Each of these files is documented. Here's what your function should look like in action:
> (load "mcm-sol.scm")
> (define A (random-mcm-problem 6 20))
> A
#6((17 15) (15 13) (13 8) (8 3) (3 7) (7 16))
> (mcm-sol A)
2814
> (table-print bestK)
-1 0 0 0 3 3 -1 -1 1 1 3 3 -1 -1 -1 2 3 3 -1 -1 -1 -1 3 3 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1
> (best-parens 0 5) (((0) ((1) ((2) (3)))) ((4) (5)))

A Dynamic Programming Solution
The idea behind the dynamic programming solution is that we change our view of the problem to that of simply trying to get the table filled in. In the memoized version, filling in T[i,j] requires recursive calls based on:
t = fmm(A,i,k) 
       + fmm(k+1,j) 
       + rows(Ai)*cols(Ak)*cols(Aj);
... where i ≤ k < j. That corresponds to needing table entries
  T[i,i], T[i,i+1], ..., T[i,j-1]
T[i+1,j], T[i+2,j], ...,   T[j,j]
	
If you look at the diagonal (I mean upper-left to lower-right) on which T[i,j] lies, you'll see that all the table entries we need lie below that diagonal. So, we'll fill in our table from the "0th diagonal", i.e. the one that runs from the upper-left corner to the lower right corner, followed by the 1st diagonal, i.e. the one just above the 0th, and continuing until the (n-1)st diagonal, which consists solely of the upper right cell in the table.
This table shows the entries required to fill in T[i,j]. Notice that they all all below the diagonal on which i,j falls.
So we'll fill in our table entries a diagonal at a time, starting from diagonal d=0 and progressing to diagonal d=n-1. Each diagonal gets filled in from top (i.e. row i=0) to bottom (i.e. row i=n-1-d). We like to think of table entries as row i and column j, not diagonal d and row i, so it'd be nice if we could figure out j from d and i. The row i entry on diagonal 0 is clearly T[i,i]. The row i entry on diagonal 1 is clearly T[i,i+1]. Follow the pattern and we see that the row i entry on diagonal d is j=i+d.

Now, once we decide on a table entry T[i,j] to fill in, how do we come up with a value? We just use the original fmm exactly as always, except that the recursive calls are replace with table look-ups, since we know the values we need are already in the table. Below you'll see the dynamic programming solution to this problem, along with the memoized and original algortithms. Pay attention to how both the memoized and the dynamic programming versions of fmm simply wrap the original fmm algorithm in some code that manipulates tables.

Original Recursive Algorithm Memoized Version Dynamic Programming Version
int fmm(A,i,j)
{  
  int m = -1;
  if (i == j) 
    m = 0;
  else
  {
    for(int k = i; k < j; ++k)
    {
      t = fmm(A,i,k) + fmm(A,k+1,j) 
          + rows(Ai)*cols(Ak)*cols(Aj);
      if (m == -1 || t < m)
        m = t;
    }
  }
  return m;
}
int fmm(A,i,j)
{  
  if (T[i,j] == -1)
  {
    int m = -1;
    if (i == j) 
      m = 0;
    else
    {
      for(int k = i; k < j; ++k)
      {
        t = fmm(A,i,k) + fmm(A,k+1,j) 
            + rows(Ai)*cols(Ak)*cols(Aj);
        if (m == -1 || t < m)
          m = t;
      }
    }
    T[i,j] = m;
  }
  return T[i,j];
}
int fmm-dynamic(A,n)
{
  T = nxn table, all values initialized to -1
  for(d = 0; d < n; d++)
  {
    for(i = d; i < n; i++)
    {
      j = i - d;
      int m = -1;
      if (i == j) 
        m = 0;
      else
      {
        for(int k = i; k < j; ++k)
        {
          t = T[i,k] + T[k+1,j]
              + rows(Ai)*cols(Ak)*cols(Aj);
          if (m == -1 || t < m)
            m = t;
        }
      }
      T[i,j] = m;
    }
  }
}
Notice how the original fmm code (i.e. the code in blue) pops up in both the memoized and dynamic progrmmming versions.

Augmenting fmm to recover the optimum parenthesization
The file mcm-sol.scm implements our scheme for recovering the optimum parenthesization. In addition to the previous table fewT that memoizes fmm, we have the table bestK, which holds our best split values. I.e. bestK[i,j] = k such that the fewest multiplications in computing the product Ai...Aj results from the outermost parenthesization (Ai..Ak)(A{k+1}..Aj).
> (mcm-sol (random-mcm-problem 5 10))
160
> (table-print bestK)
-1  0  0  2  2 
-1 -1  1  2  2 
-1 -1 -1  2  2 
-1 -1 -1 -1  3 
-1 -1 -1 -1 -1 
> 

Recovering the Optimum Parenthesization
OK, we augmented the memoized fmm so that it stored the best "k" values in a table. In particular, it produced the table bestK such that
bestK[i,j] = the "k" value that produces the fewest multiplications when computing the product Ai..Aj.
The file mcm-sol.scm implements this in scheme. Here's a sample run for 5 random matrices:
> (mcm-sol (random-mcm-problem 5 10))
160
> (table-print bestK)
-1  0  0  2  2 
-1 -1  1  2  2 
-1 -1 -1  2  2 
-1 -1 -1 -1  3 
-1 -1 -1 -1 -1 
> 
Using bestK, we can recover the parenthesization that produced the fewest multiplications in computing A0 A1...An.

start withfind best kresulting parenthesization
A0 A1 A2 A3 A4
_|__0__1__2__3__4_
0| -1  0  0  2  2 
1| -1 -1  1  2  2 
2| -1 -1 -1  2  2 
3| -1 -1 -1 -1  3 
4| -1 -1 -1 -1 -1
(A0 A1 A2)(A3 A4)
(A0 A1 A2)(A3 A4)
_|__0__1__2__3_4_
0| -1  0  0  2  2 
1| -1 -1  1  2  2 
2| -1 -1 -1  2  2 
3| -1 -1 -1 -1  3 
4| -1 -1 -1 -1 -1
((A0)(A1 A2))(A3 A4)
Optimum parenthesization is ((A0)(A1 A2))(A3 A4)

Now, the interesting problem is to write an algorithm that can recover this parenthesization from any given table bestK.


Christopher W Brown
Last modified: Mon Mar 28 12:55:36 EST 2005