What to submit and when:

- All submissions are electronic: by e-mail to elenam at morris.umn.edu and CC to all lab partners. Please do not delete your e-mail from "Sent mail" or your mailbox until the end of the semester.
- When working on the lab, please comment your work so that it is clear what contributions of each person are.
- At the end of the lab each group should send me the results of their in-class work. Please indicate if this is your final submission.
- If your submission at the end of the lab time was not final, please send me(CC to the lab partner(s)) a final copy before the due time. Please use the subject "3501 Lab N", where N is the lab number.

Work in pairs

The goals of this lab are:

- To study principles of dynamic programming
- To implement a dynamic programming solution

Study and implement the algorithm for finding an optimial
parenthesization for matrix multiplication (section 15.2 p. 331). You
don't need to actually multiply matrices.

The algorithm takes an ordered list of matrix dimensions and produces
positions of parentheses (or, better yet, their visual representation, i.e.
shows where the parentheses are going to be placed in the list).
The algorithm must also produce the total number of element multiplications
performed. Use an
example 15.2-1 for testing.

Exercise 15-6 p. 368: moving on an N*N checkerboard. We assume that the bottom row of the checkerboard has squares indexed [1,1]...[1,N], the second row is indexed [2,1]...[2,N], etc. Your program reads N (the checkerboard dimension) and three matrices of payoffs for moves:

- An (N-1)* N matrix U of payoffs for going directly up. U[i,j] is the amount that you get by going from a square [i,j] to [i + 1, j].
- An (N-1) * (N-1) matrix L of payoffs for going up left. L[i,j] is the amount that you get for going from [i, j + 1] to [i + 1, j].
- An (N-1) * (N-1) matrix R of payoffs for going up left. R[i,j] is the amount that you get for going from [i, j] to [i + 1, j + 1].

For instance, the following matrices represent a 4*4 checkerboard. Note that the payoffs corresponding to the bottom row are in the top row of the matrices.

U: 3 2 1 4 2 2 1 -2 1 3 4 1 L: 1 2 1 3 1 -1 2 0 1 R: 2 3 1 0 1 0 2 3 -1

For instance, the payoff for going from [1,3] up to [2,3] is 1, for going up left to [2,2] is 2, and for going up right to [2,4] is 1.

Your program must find and output the optimal path on the checkerboard (the list of squares) and the corresponding total amount collected. Use the example above as one of your test cases, include the answer for it in comments.

Your task is to implement a dynamic programming solution. You may start with a recursive (i.e. inefficient!) solution that you can use as a test case, but your final solution must be loop-based, not recursive.

What is the run-time efficiency of your algorithm? Please justify your answer.

Submit your program code and a clear description of how to run it (examples help). Also include your run-time efficiency analysis.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.