These are the hints that were posted Tuesday.
You until Thursday to do them, for a 50% reduction 
in credit.

These comments should not be considered complete solutions.
They should be viewed as ideas to be incorporated into complete
solutions.

Problem 4 (a).

Let OPT[i,j] be the cost of the optimal static tree for elements i,
i+1, ... j (a set we denote by [i,j]).  Call the property stated in
part 4(a) Claim 4(a).  The following is called Claim 1, which was
given in the hint:

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

Claim 4(a) can be derived from the following simpler statement:

  Claim 2: if r is an optimal root for [i,j] then there is an
           optimal root r' for [i,j+1] such that r' >= r.

So the approach to the problem is to prove claim 1.  Now, assuming
claim 1, prove claim 2.  Now assuming claim 2 prove claim 4(a).  Now
assuming claim 4(a), solve part 4(b).

Here are some comments on these parts:

   claim 2 ==> claim 4(a)

   This is fairly trivial, if you make use of a symmetric version of
   claim 2, where you move the left endpoint of the interval.


   claim 1 ==> claim 2

   Say we fix a root r for the interval [i,j], and build optimal left
   and right subtrees for this root.  What happens when we grow the
   interval on the right, and keep the same root?  Adding this new
   node will increase the cost.  Call the increase in cost Delta(r).
   Let r' be some root to the left of r.  So r' < r.  Show that
   Delta(r') > Delta(r) using claim 1.


   proof of claim 1:

   Perhaps this is the hardest part.  I'll just say that it's by
   induction.  And one of the base cases is the claim that
   OPT[i,j]+OPT[k,l] <= OPT[i,l], assuming that i <= j < k <= l.
   Which also requires proof.



Problem 5(a).

Mimic the proof of the static finger theorem.

Problem 5(b).

The first thing to do is note that the graph is largly irrelevant.
The relevant part is the shortest path tree in that graph from the
special node s to all other nodes.  The graph distances from s to any
node is just the distance in this tree.

Assign weights to all the nodes in the tree.  Then use the access
lemma applied to these weights.  The number of children of any node is
at most Delta.  Choose the weights so that the sum of all the weights
is at most 1, and the weight of a node at distance d from s is 
some quickly decreasing function of d.


Problem 6.

First of all, it's important in many correct solutions to this problem
to have a good solution to exercise 1.  So let's discuss that for a
minute.  The cleanest solution (that I know) is to first compute the
preorder numbering of each node.  The following function does this,
(and keeps the answer in a field called min().)  It also computes
another field called max().  max() is the maximum preorder number of
any node in the subtree rooted at a node.

            count = 0;
            preorder_label(root);

            function preorder_label(t) {
               count = count+1;
               min(t) = count;
               for each child c of t do {
                  preorder_label(c)
               }
               max(t) = count;
            }

Now a node x is an ancestor of a node y if and only if y's _interval_
[min(y),max(y)] is contained in x's.  This solves exercise 1.

Now on to problem 5.  First of all, we can root the tree at an
arbitrary node.  This does not change the distance metric.  And we can
label each node with its depth in the tree (distance to the root).
Let p(x) denote this distance label.

Given two nodes x, and y, if we can find their lowest common ancestor
A (the common ancestor farthest from the root) then we are done.
d(x,y) is simply p(x)+p(y)-2p(A).

So the problem reduces to that of quickly finding the lowest common
ancestor of x and y.  One approach to doing this (which leads to
log^2(n) search time) is to build a data structure that allows you to
do binary search on the depth to find the LCA (lowest common
ancestor). 

Another approach involves partitioning the tree into paths.  Say we've
computed the _size_ of each node.  As in splay trees, the size of a
node is the number of nodes in the subtree rooted there.  Call an edge
from a node c to its parent x _heavy_ if size(c) > (1/2)size(x).  Call
an edge _light_ if it is not heavy.  Why are the following properties
true?

  (1) Among all the edges from x to its children, at most one of them
      can be heavy.

  (2) On the path from any node to the root, at most floor(log(n)) of
      the edges can be light.

Prove that these are true.  Now make use of this partitioning of the
tree into _heavy paths_ to solve the problem.  (These ideas actually
lead to a somewhat simpler solution if you don't try to compute the
LCA, but just the distances.)