Assignment 2 hints:

Problem 4: First some notation.  Let OPT[i,j] be the cost of the
optimal static tree for a range of elements [i...j].  In other words,
if we restrict the access sequence to just those elements in the range
[i...j], and build the optimal static tree just for those elements,
then OPT[i,j] is the total cost (number of comparisons) done when
accessing those elements in the sequence.

You should have written a recurrence for OPT[i,j] as part of your
solution to exercise 3.

Hints for 4(a): The first hint is that yes, the result is true.  The
second hint is that it helps to first prove the following claim:

  Claim: let i <= j <= k <= l.  Then OPT[i,l]+OPT[j,k] >= OPT[i,k]+OPT[j,l],

This claim seems a lot less "obvious" than the question in the hwk,
but it is easier to prove and serves as a useful stepping-stone.