Analysis of Algorithms : An Active Learning Approach

9.3 DYNAMIC PROGRAMMING 255

BiCoeff[N, k]. The following algorithm gives the dynamic programming
solution to this problem:
for i = 0 to N do
for j = 0 to minimum( i, k ) do
if j = 1 or j = i then
BiCoeff[ i, j ] = 1
else
BiCoeff[ i, j ] = BiCoeff[ i-1, j-1 ] + BiCoeff[ i-1, j ]
end if
end for j
end for i

Here the recursive algorithm would calculate

terms, and the dynamic programming version would only calculate O(N*k)

terms.

■ 9.3.2 Dynamic Matrix Multiplication

If you have a series of matrices, each having a different dimension, which need

to be multiplied together, the order in which the multiplication is done can

have a dramatic impact on how quickly this is accomplished. For example, if

we have four matrices that we will call M 1 ,M 2 ,M 3 , and M 4 , and they have sizes

of 20  5, 5  35, 35  4, and 4  25, respectively, there are five different

ways that they can be multiplied together that will take from 3100 to 24,500

multiplications. The full details are given in Fig. 9.7. This figure shows various

ways in which these can first be paired, then the ways in which three of the

matrices can be multiplied, and finally the ways that all four can be multiplied

together. The final column shows the number of multiplications necessary to

achieve the multiplication order of the first column. You should recall that to

multiply a matrix of size AB by a matrix of size BC will take A*B*C

multiplications.

The following algorithm will build an upper triangular matrix with the

minimum costs from Fig. 9.7. The size of matrix Mj is given as sjsj+1. The

minimum cost will be in location cost1,N (in other words the upper right

location) at the completion of this algorithm. This algorithm will also calculate

2 N

k

* –^1