How to find worst case in chain matrix multiplication The question we got was Determine a worst-case parenthesization of the matrix-chain product whose sequence of dimensions is (5, 2, 3, 10, 4, 6, 7, 8). 
 what i dont understand is how do we determine how to place the brackets to get the worst possible case
 A: The cost of a matrix-matrix multiplication of dimensi0ns $a\times b$ multiplied with $b\times c$ is $ac$ elements each computed with $b-1$ additions and $b$ multiplications, i.e. $ac(2b-1)$.
This means $C(a,b,c) = ac(2b-1)$. The parentheses in a chain correspond to the order in wich inner dimensions are removed from the chain by performing such an operation.  
For example the chain $(3,4,2,2)$ has two possible orders,
$(3,4,2,2) \to (3,2,2) \to (3,2)$ with cost $C(3,4,2) + C(3,2,2) = 60$
or $(3,4,2,2)\to(3,4,2) \to (3,2)$ with cost $C(4,2,2) + C(3,4,2) = 66$
You can do the same for your chain of $8$ dimensions, i.e. $6$ inner dimensions with $6!$ possibilities (some of them equivalent) or you can try to use your intuition (try to bring up large matrices, i.e. subchains $(a,b)$ with $a,b$ as large as possible) to maximize the number of elementary operations needed.

Solution
There are $10$ optimal solutions (i.e. orders of multiplication with the maximum operations needed). The total cost is $3285$ and one such sequence is this one:
$$(5,2,3,10,4,6,7,8) \to (5,2,3,10,6,7,8) \to (5,2,3,10,7,8) \to (5,2,3,10,8) \to (5,3,10,8) \to (5,10,8) \to (5,8)$$
Another (probably even more intuitive) soltution with the same cost is this:
$$(5,2,3,10,4,6,7,8) \to (5,3,10,4,6,7,8) \to (5,10,4,6,7,8) \to (5,10,6,7,8) \to (5,10,7,8) \to (5,10,8) \to (5,8)$$
I found these using a small matlab script wich describes the order of operations by a sequence in $[6]\times [5]\times \ldots \times [2] \times \{1\}$ with the $i$-th index giving the number of the inner dimension to remove, $[n]:=\{1,\ldots,n\}$. The above solutions are thus represented as $[4,4,4,1,1,1]$ and $[1,1,2,2,2,1]$ respectively.
seq = [5 2 3 10 4 6 7 8];
cost = @(a,b,c)a.*c.*(2*b-1);
[o1,o2,o3,o4,o5,o6] = ndgrid(1:6,1:5,1:4,1:3,1:2,1);
ops = [o1(:) o2(:) o3(:) o4(:) o5(:) o6(:)];
c = zeros(720,1);
for i=1:720
    s = seq;
    for o=1:6
        c(i) = c(i) + cost(s(ops(i,o)), s(ops(i,o)+1), s(ops(i,o)+2));
        s(ops(i,o)+1) = [];
    end
end
optops = ops(c == max(c),:);

