Homework Exercise 3

Due: by 6pm on Tue 14 Oct
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. Consider a rat that is being trained to navigate an n × n grid. The rat starts in position (1,1) (the upper-left corner) and at each step, moves either one location down or one location right, i.e., from position (i,j), the rat can move to positions (i+1,j) or (i,j+1), assuming the subscripts are within range — the rat cannot move along diagonals or double-back and move left or up. Furthermore, suppose that each of the grid positions (i,j) contains a piece of cheese of weight w(i,j), a positive integer. The rat wants to get to position (n,n) having consumed as much cheese as possible.

    Follow the paradigm developed in class to design a Dynamic Programming algorithm that determines the maximum total amount of cheese that the rat could consume in its traversal of the grid, and to compute a traversal that achieves this maximum. Justify that your recurrence and the resulting algorithm are correct.