CSci 3501 Algorithms and Computability - Lab 11.

December 3rd. Due Wednesday, December 9th at 11:59pm

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.

Lab assignment

Work in pairs

Lab overview and goals

The goals of this lab are:

1. To study principles of dynamic programming
2. To implement a dynamic programming solution

Problem 1

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.

Problem 2

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.

What to submit

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

CSci 3501 course web site.