===========================================================================
CSC 373H1 / L0101      Tutorial Notes -- Week  5            Winter 2012
===========================================================================

Point out that on the course homepage is a section
on "Past Exams" in CSC373.  This is a great place to get study
questions.
 
For example, following the link "Previous Exam Study Guide" on
the course homepage, gives a table of questions from old exams 
with a breakdown into various topics.  
 
For example, question 4 of the first exam, csc373h-d06.pdf, in
that table poses the following dynamic programming problem (use
the same pdf password as the notes to open these exams).
 
See Q4_dynProg_csc373h-d06.pdf (no password required).

=========================
Introduce a CLARIFIED problem: 
  Replace all instances of "week" with "month".  Choose 
  one project per month, and you are allowed to choose the
  internet project each month if you want. 

Let T(k,j) be the bottom two rows of the table of payoffs given 
in Question 4, with k = 0, 1  representing toronto, vancouver, 
respectively.  And let I(j) be the internet job payouts
in the first row of the same table.
 
Discuss the idea of using a 2 x (n+1) array P(k,j) 
which stores max-profit at the end month j given that 
you are working in city k (=0,1) during month j.  

Since you have to start in city Toronto (k=0), the first
columns of the matrix might look like:

       0        1       2      ....  5
T:0    0      P(0,1)    ...
V:1   -infty  P(1,1)    ...

(-infty can be replaced by -(#weeks + 1) * maximum payoff in the tables
T or I given in the question.... just make sure it is negative enough
never to be selected.)

How do we compute P(0, j) (profit, if we worked in toronto on week j > 0)?
Ask for suggestions...

P(0,j) = max( P(0,j-1) + T(0,j)  (in Toronto prev month, stay, 
                                  do toronto job month j),
              P(0,j-1) + I(j), (in Toronto prev month, stay, 
                                do internet job month j),
              P(1,j-1) - C + T(0,j)   (in Vancouver prev month, fly to toronto, 
                                do toronto job month j),
              P(1,j-1) -C + I(j), (in Vancouver prev month, move to Toronto, 
                                do internet job month j)
            )

We could simplify this by removing the case in which we move
cities before doing an internet job, with the increase in profit
being I(j) - C, since this term will never be the max in the above
expression.
                          
So, in general, for k = 0 or 1, j>0,

(*)  P(k,j) =  max{ P(k, j-1) + T(k,j),  
                    P(k, j-1) + I(j), 
                    P( not k, j-1) - C + T(k, j) }

============

Variations:

a) How would you compute an optimal solution given the
table P of profits?
 
b) Sketch a correctness proof.  Use the induction hypothesis
L(j):  P(0,j) and P(1,j) equal the maximum profits obtainable
given that you work in city 0 (or 1, respectively) on month j,
or, if this is impossible, P(k,j) = -infty.

Note the base case L(0).

Note the proof of the induction step requires a verification of the 
recurrence relation (*), GIVEN the induction hypothesis L(j-1).
 
a) How would you change the above solution if you were only allowed
to do at most one internet project (over all the months)?
(The original problem wasn't too clear on this.)
 
========

Remind them to look up the links in the "Past Exams" section
of the homepage for sample exam questions.