CS19002 Programming and Data Structures Laboratory Spring 2010, Section 5

Assignment 3

You are given n matrices A1, A2, ..., An. The dimensions of the matrices are stored in an array D[] of size n+1. The i-th matrix Ai has dimension Di-1 x Di, so the product A1A2...An 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 A1A2...An of the given n matrices. Let the minimum effort for the product Ai+1Ai+2...Aj 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) + DiDkDj | 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 A1A2...An. Print this minimum effort.

Report the output of your program for n = 20.

Sample output

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

A note on random numbers

Lab Home Submission Site My Home