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.)