SI433 Class 11:

Reading
Section 16.1.

Homework
Finish Project!

Lecture
Review Homework
Take a look at my solution to HW#10.

Where were we ...
Last class we discussed the Matrix Chain Multiplication problem, i.e. find the parenthisization of matrices A1, A2, ..., An that allows us to compute their product with the fewest possible multiplications.

I decided that we'd tackle a slightly easier problem first: Given matrices A1, A2, ..., An, what is the fewest multiplications required to compute the product of the Ai's? We devised a terribly inefficient recursive algorithm that solved this problem. Here's an implementation of that algorithm. Note that it relies on the file Matrix.h.

Memoize it
Faced with an inefficient algorithm that keeps computing the same thing over and over, we might try memoization. Here's an implementation of that algorithm.

Be Dynamic
Memoization says "I want to solve FM(A1,...,An), I'll do it recursively, saving subresults in a table as I go. A side effect of this computation is that I fill up the table." Dynamic programming flips things around and says "I want to fill in the table. As a side effect I'll solve FM(A1,...,An). We fill in that table starting on the main diagnonal. Once that's filled we move up a diagonal and fill it in, which requires us to know the entries on the main diagonal ... which we do. We keep moving up and up through diagonals until we get to the top right entry, which is the answer we really want. Here's an implementation of that algorithm.


Asst Prof Christopher Brown
Last modified: Tue Feb 13 15:58:51 EST 2001