Tutorial 10
===========

Here's an example of matrix grouping that follows the form of
Assignment 4, except it uses bottom-up DP rather than memoization.

Notice that the notation differs from that in the Course Readings.
The reason is that Assignment 4 makes all three problems have
compatible notation (the indices get shifted), in order to make it
easier to have a generic algorithm.

Here are the dimensions of five matrices:

        A0 is a 3x5 matrix
        A1 is a 5x4 matrix
        A2 is a 4x6 matrix
        A3 is a 6x7 matrix
        A4 is a 7x3 matrix


C[i][j] is the table of optimal values (fewest multiplications) for
multiplying matrices Ai ... A(j-1) (the -1 is where the notation
differs from the Course Readings).  The table C[i][j] is zero if j is
less than i+2, so we fill in only the relevant part.  The first step
is when j = i+2, which is the cost of multiplying matrices i and i+1
together.  Formally, it is C[i][i+1] + C[i+1][i+2] + w(i,i+1,i+2) ---
the first two terms are zero, and the last is the product of the
number of rows in Ai, A(i+1), and A(i+2).

But what is w(3,4,5), since we don't have a matrix A5?  Well, the
number of rows in A5 (if it existed) would be the same as the number
of columns in A4.  So we can either add a dummy matrix with the
appropriate number of rows, or remember to make this substitution,
giving w(3,4,5) = 6*7*3.

Also record the k for which C[i][k] + C[k][j] + w(i,k,j) is a minimum,
by writing |k after the entry C[i][j]

          j     2       3       4       5
        i |     
        --+--------------------------------------
        0 |     60|1            
        1 |             120|2
        2 |                     168|3
        3 |                             126|4



Now we fill in the next diagonal (j = i+3), which is the minimum cost
of multiplying matrices i, i+1, and i+2 together.  This will be the
minimum of C[i][i+1] + C[i+1][i+3] + w(i,i+1,i+3) and C[i][i+2] +
C[i+2][i+3] + w(i,i+2,i+3) (product of number of rows of Ai, A(i+2),
A(i+3).

          j     2       3       4       5
        i |     
        --+--------------------------------------
        0 |     60|1    132|2   
        1 |             120|2   308|2
        2 |                     168|3   198|3
        3 |                             126|4



Next we fill in the diagonal where j = i+4.  Now we take the minimum
of:
        C[i][i+1] + C[i+1][i+4] + w(i,i+1,i+4)
        C[i][i+2] + C[i+2][i+4] + w(i,i+2,i+4)
        C[i][i+3] + C[i+3][i+4] + w(i,i+3,i+4)

... for each of the two entries.  

          j     2       3       4       5
        i |     
        --+--------------------------------------
        0 |     60|1    132|2   258|3   
        1 |             120|2   308|2   258|2
        2 |                     168|3   198|3
        3 |                             126|4



Finally, we fill in the entry where j = i+5 --- there's only one of
those.  But we need to consider the minimum over more sums:

        C[i][i+1] + C[i+1][i+5] + w(i,i+1,i+5)
        C[i][i+2] + C[i+2][i+5] + w(i,i+2,i+5)
        C[i][i+3] + C[i+3][i+5] + w(i,i+3,i+5)
        C[i][i+4] + C[i+4][i+5] + w(i,i+4,i+5)

          j     2       3       4       5
        i |     
        --+--------------------------------------
        0 |     60|1    132|2   258|3   294|2
        1 |             120|2   308|2   258|2
        2 |                     168|3   198|3
        3 |                             126|4


Working backwards, the entry for C[0][5] says we can achieve a minimum
cost of 294 multiplications if we split between matrix 1 and 2, at the
top level:

        (A0 A1)(A2 A3 A4)

C[2][5] says we can achieve a minimum cost of 198 multiplications in
the right factor if we split between matrix 2 and 3:

(A0 A1)(A2 (A3 A4))

This is the optimal matrix grouping.