CS19002 Programming and Data Structures Laboratory |
Spring 2010, Section 5 |

You are given *n* matrices *A*_{1}, *A*_{2},
`...`, *A*_{n}. The dimensions of the matrices
are stored in an array *D*[] of size *n*+1. The *i*-th
matrix *A*_{i} has dimension
*D*_{i-1} x *D*_{i},
so the product *A*_{1}*A*_{2}`...`*A*_{n}
can be computed. If *A* is an *r* x *s* matrix
and *B* an *s* x *t* matrix, then computing the
product *AB* requires *rst* multiplications and *rst* additions
of elements. Let us say that the effort associated with computing the
product *AB* is *rst*. For computing the product of more than two
matrices (of compatible dimensions), the total effort may depend on the
order in which the matrices are multiplied. For example, suppose that
*A*, *B* and *C* are *r* x *s*,
*s* x *t* and *t* x *u*
matrices. Then the effort associated with (*AB*)*C* is
*rst* + *rtu*, whereas the effort associated with the
computation *A*(*BC*) is *rsu* + *stu*.
These two total efforts are different, in general. For eample, if
*r*=5, *s*=6, *t*=7 and *u*=4, then
*rst* + *rtu* = 350,
whereas *rsu* + *stu* = 288. This means that
it is preferable to compute *ABC* as *A*(*BC*) (instead of
(*AB*)*C*).

In this assignment, you write a recursive program to compute the
minimum total effort needed to compute the product *A*_{1}*A*_{2}`...`*A*_{n}
of the given *n* matrices. Let the minimum effort for the product
*A*_{i+1}*A*_{i+2}`...`*A*_{j}
be denoted by *C*(*i*,*j*). Note that the dimensions of these
*j*-*i* matrices are stored at indices *i* through *j*
in the array *D*[]. We have the following recursive definition of
the minimum efforts.

*C*(*i*,*i+1*) = 0 (no effort for one matrix), and

*C*(*i*,*j*) = min(*C*(*i*,*k*) + *C*(*k*,*j*) + *D*_{i}*D*_{k}*D*_{j} | *i*+1<=k<=*j*-1)
(multiply matrices *i*+1 through *k*, matrices *k*+1 through *j*, and finally the two sub-products; vary *k*, and take the minimum).

Write a **recursive function** that takes three inputs: the dimension array *D*,
and indices *i* and *j*. The function should return the minimum
effort *C*(*i*,*j*).

In the main function, read the number *n* of matrices.
Generate the *n*+1 entries of the dimension array *D*
*randomly* between 1 and 9. Print the dimensions of the matrices.
Then call the recursive function mentioned above to compute the minimum
effort associated with the product *A*_{1}*A*_{2}`...`*A*_{n}.
Print this minimum effort.

Report the output of your program for *n* = 20.

How many matrices? 3 The dimensions are 5x6 6x7 7x4 The minimum effort for the product is 288

Lab Home | Submission Site | My Home |