cs209 lab8

cs209 lab8

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l8.html

For this lab you should submit all source code (PYTHON files), and the result(s) of running the program on (a few) test cases. The source code must be well presented (indenting, spaces, reasonable variable/function names, etc.) and must include comments (as a rough guideline - aim to have nearly as many comments as lines of code).
The above material should be uploaded to BLACKBOARD before the deadline of 5pm Monday 18nd. March 2013. You will lose 20% for each day (or part of day) the lab is late. (In BLACKBOARD, you should attach your PYTHON program under "Attach File" in the section "2. Assignment Materials". If you are including anything other than PYTHON code, e.g. answers to questions, etc, it can be cut/pasted in to "Submission" under "2. Assignment Materials".) If any of this is unclear, you should ask the Teaching Assistant in the lab.
Plagiarism (the unattributed copying of work from other sources (internet, fellow students,....)) will not be tolerated. Please see http://www.nuigalway.ie/engineering/documents/plagiarism_guide_students _v4.pdf. You risk getting zero for your lab if it is found to be plagiarized.

This lab is based on the dynamic programming solution to the matrix multiplication problem covered in lectures. You can use as a starting point the program matrix.py handed out at lectures or available at http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/. For other reading on this problem, there are many good sources on the internet, for example:

http://en.wikipedia.org/wiki/Matrix_chain_multiplication

http://www.seas.gwu.edu/~ayoussef/cs212/dynamicprog.html

http://www.columbia.edu/~cs2035/courses/csor4231.F11/matrix-chain.pdf

http://www.cs.sunysb.edu/~jgao/CSE548-fall07/David-mount-DP.pdf

For this week, you should modify the matrix.py program so that

It is "nicer": i.e., it has comments, variable/function names are well chosen, it reads the matrix dimensions in from the user and prints out the resulting optimum no. of multiplications. (Also - come up with some other systematic way of replacing the large number MAX by some other large number (dependent on the list of matrix dimensions) that is guaranteed to be large enough.)
As well as calculating the fewest no. of multiplications, it also calculates the worst case (largest no. of multiplications). You should report the difference as a percentage (example: if the best case used 555 multiplications, and the worst case used 2220, then report "the number of products used in the best case is 25% of those used in the worst case").

Run your program on the matrix dimensions:

[10,100,15,60,1]
[4,200,10,70,90,170,2,15,35]
[5,20,5,21,5,20,5,21,5,20,5]

and submit these three answers.