91.404/583-Algorithms: Project 2

. Dr. Haim Levkowitz
Date: November 20, 1996

Due: Wednesday, December 11, 1996 (last class)

Submit:

 submit haim algs_proj_2  list of files

Consider the matrix-chain multiplication problem discussed in Section 16.1, and solved via dynamic programming. One could try the following (``greedy'') algorithm in its place:

Given the list of matrix dimensions

(p_0, p_1_, p_2_, ... , p_n_) (A_1_ has dimensions p_0_ x p_1_, ..., A_n_ has dimensions p_(n - 1)_ x p_n_)

Find the two successive matrices corresponding to the largest p_i_
p_(i - 1)_ x p_i_ x p_(i + 1)_ <---> A_i_ A_(i + 1)_
Remove p_i_ (which can be neither p_0_ nor p_n_) from the list and repeat until the list has just two elements (p_0_ and p_n_).

This will obviously give a parenthesization, and will let you compute the number of multiplications at the same time. It is sometimes optimal, and sometimes not - you are supposed to provide an example where the optimality breaks down.

The rationale behind this method is that leaving ``large multiplications'' for later will probably make the same multiplier appear twice in the products rather than just once.

The ``greedy'' algorithm works well enough often enough so that one can ask the following question:

Over a large number of such matrix chains, how far from optimal is the ``greedy'' algorithm? (e.g., the number of multiplications implied by ``greedy'' divided by the number of multiplications implied by dynamic programming).

As n increases, is this ``proportional distance'' constant, or is it a function of n?

Given that the ``greedy'' algorithm runs in time O(n^2) - while the dynamic programming one requires O(n^3) - is it reasonable to use the ``greedy'' one over the dynamic programming one? This question requires that we estimate the relative cost of being ``wrong'' against the extra computation required for being ``right.''

Languages accepted: C, C++, Pascal, Perl, Java.

Grading

Program MUST run and perform the required behavior to be considered for any grade > 0.

Running program, performing all expected behavior and exhibiting reasonable robustness: 50 pts. (I may test it, so..)
Documentation: 20 points.
Program Legibility and clarity: 20 points - this means, among other things, that any clever idiom peculiar to your choice of language MUST be explained.
``Impress me'': 10 points.

Alternative Project

Propose your own project, of similar complexity.

Back to 91.404/583-Algorithms Syllabus

Dr. Haim Levkowitz

haim@cs.uml.edu

UMass Lowell Department of Computer Science