CSC 715 Assignment 2

Due date: Tuesday, February 9, 2010, 10:00 AM.

1. If f(n) = log log n, what is f*(n)? Prove your answer.
2. What is the solution to the recurrence F(n) = (n/log log n)F(log log n) + n
   Error corrected: Tue Feb 2 12:53:21 PST 2010
3. Suppose A is a Monge matrix with p rows and q columns, and that B is a Monge matrix with q rows and r columns. Prove that the tropical matrix product AB is a Monge matrix.
4. Suppose that G is a weighted directed graph where
   1. The vertices of G are labeled v₁ ... v_n .
   2. If i < j there is an edge from v_i to v_j of weight (j-i)² + 10. There are no other edges.
   For any m, let G^m be the n by n matrix where G^m_ij is the smallest weight of any path of length exactly m from v_i to v_j .
   Length of a path is defined to be the number of edges.
   If there is no path of length exactly m from v_i to v_j , then G^m_ij is infinity.
   Prove that G^m is a Monge matrix.
5. We now consider a different version of the Traveler's Problem. As before, the traveler can travel no more than a given distance each day, and must stay at an inn during each night, and each inn has some cost.
   But now, we assume that all the inns are located on a semi-circle, and that the traveler can travel between inns using straight line paths instead of sticking to the circle, as illustrated here in postscript format (eps) and in portable document format (pdf).
   The traveler carries a heavy backpack, and thus he imputes a "carrying cost" proportional to the distance he walks. Instead of just minimizing room costs, the traveler wants to minimize his total cost, which is the room cost plus the carrying cost, which he imputes to be one copper piece per furlong.
   
   Explore this problem.