===========================================================================
CSC 373H1 / L0101      Tutorial Notes -- Week  6           Spring 2012
===========================================================================

Outline:

1. Go over the assignment, any common difficulties.  
One question I had was how much can they expect to skip in their
answers.  I said to make sure they prove in detail a few
major points.  (We want to see they can carry out a proof.)  For 
other things they can clearly sketch the main ideas behined
the proof, and omit the details.  This is what I did in the
solution.

2. Consider the problem in longestIncSubsequence.pdf

First go over the statement of the problem, without introducing q(k) 
(since q(k) gives away most of the solution).

Get them to think about possible approaches for dynamic programming
solutions.  

EG: First think in terms of OPT(k) == length of longest increasing 
subsequence (LIS) within (x(1), ... x(k)).  Explain why it is hard
to write OPT(k) in terms of OPT(j) for j < k.  That is, two cases
are:
1) x(k) is not used in the LIS of (x(1), ... x(k))
2) x(k) is used.
These two cases lead to (for k>=1, here OPT(0) == 0)
  OPT(k) = max{ OPT(k-1), 1 + length LIS in (x(1), ... x(k-1)) for 
                          which the maximum (last) item is less than x(k) }

The clause "for which the maximum... less than x(k)" is a different
subproblem... and would require further processing.  We don't want that.
 
Key Idea: Keep track of the maximum value of increasing subsequences,
and keep track of the length.
The max value is just x(j) for the last value in the sequence.  The
length... why not store it in an array at index j?

This leads directly to q(k) as defined in longestIncSubsequence.pdf.

Derive the recurrence relation for  q(k) shown
in part a of longestIncSubsequence.pdf.  Make sure they 
understand this solution.

Do part b of this question.  (Extract length(LIS) from the array q)

Do part c if there is time.  (Extract a LIS for x using arrays q and x)