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.