CSci 3501 Algorithms and Computability - Lab 11.

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

What to submit and when:

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:

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.

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.