I think the Java Matrix Chain Multiplication algorithm on Wikipedia is incorrect

Question

I am nearly certain the Java implementation of matrixChainOrder on the Wikipedia page, Matrix Chain Multiplication, is incorrect. I would change it but I am not a well qualified Mathmematician and am not comfortable making the change without first vetting my observation. I guess what I'm asking is - am I correct in this assertion? k should instead be k + 1 because this version is written in zero based indexes unlike the pseudocode version first introduced on the same page.

protected int[][]m;
protected int[][]s;
public void matrixChainOrder(int[] p) {
    int n = p.length - 1;
    m = new int[n][n];
    s = new int[n][n];

    for (int ii = 1; ii < n; ii++) {
        for (int i = 0; i < n - ii; i++) {
            int j = i + ii;
            m[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k + 1; // <-- this is the necessary change 
                }
            }
        }
    }
}

edit

I'm near answering my own question, but here's an example that explains the problem created by shifting the algorithm into a zero-based index:

Given the array = [3,2,4,3,2], these are cost tables generated by the above:

m:
0   24  42  48  
0   0   24  36  
0   0   0   24  
0   0   0   0   

s:
0   0   0   0   
0   0   1   2   
0   0   0   2   
0   0   0   0   

By not adding 1 to k (because of zero index shift), you get the wrong places for matrix chaining. You can't parenthesize the matrices at 0 for starters. The correct output for s should be:

s:
0   1   1   1   
0   0   2   3   
0   0   0   3   
0   0   0   0

s[0][3] = 1 means split ABCD at A(BCD)
s[1][3] = 3 means split A(BCD) at A((BC)D)

That's it - an optimal cost calculation.

Answer 1

No, the implementation is correct as it is. Changing s[i][j] = k; to s[i][j] = k + 1; would break the program.

You can test this by copying the code into a file called MatrixOrderOptimization.java and adding a main function like this one:

public static void main(String[] args) {
  MatrixOrderOptimization moo = new MatrixOrderOptimization();
  moo.matrixChainOrder(new int[]{ 3, 2, 4, 3, 2 });
  moo.printOptimalParenthesizations();
}

Try compiling and running the program with and without your proposed change. You'll see that making the proposed change results in invalid index values.

Why is this? Well, the solution value s[i][j] is defined as the "index that achieved optimal cost". That's what it's called in the pseudocode and that's how the Java implementation treats it.

You point out that in the pseudocode, indices start from 1 and that in the Java implementation, they start from 0. However, the meaning of s[i][j] in both cases is the index that achieved optimal cost.

If you modify the indices by adding one, you're throwing off the rest of the program. Think about it this way: instead of changing s[i][j] = k; to s[i][j] = k + 1;, change the array accesses in printOptimalParenthesizations. In each line where the code refers to s[i][j], change that to s[i][j]+1.

In other words, replace

printOptimalParenthesizations(s, i, s[i][j], inAResult);
printOptimalParenthesizations(s, s[i][j] + 1, j, inAResult);

with

printOptimalParenthesizations(s, i, s[i][j]+1, inAResult);
printOptimalParenthesizations(s, s[i][j]+1 + 1, j, inAResult);

The effect of these changes is exactly the same as your proposed change. Here we're adding one to the optimal index when we pull it out of the array, whereas you propose adding one to the optimal index when you stick it into the array.

In both cases, the value becomes incorrect and the program crashes. That's because the meaning of s[i][j] is not the optimal index plus one. It's simply the optimal index.

The Java program expects s to contain optimal indices as it understands optimal indices, meaning that they start from zero. If you alter these values by adding one, you violate the meaning of the indices and break the program.