===========================================================================
CSC 373                     Homework Exercise 3                   Fall 2008
===========================================================================

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 x 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.