Reading Assignment: Kleinberg and Tardos, chapter 4.

Problems

1. Let G=(V,E) be a connected, undirected, weighted graph, where c(e) is the cost on edge e for any edge e Î E. Let s be a particular node in V. For any T which is a spanning tree of G rooted at s, we define the total path length of T, denoted P(T), to be
   

   P(T) = å v Î V  dT(s,v),

   where d_T(s,v) is the sum of the costs along the path between s and v in the tree T. Give an algorithm for finding a spanning tree T of G rooted at s that minimizes P(T).
2. Kleinberg and Tardos, page 92, problem 10.
3. Kleinberg and Tardos, page 92, problem 11.
4. Extra Credit: Kleinberg and Tardos, page 94, problem 15.
5. Extra Credit: Feedback on Sections 3.3-3.4 and 4.1 in book. Please submit this by email to both Erik and Anna.

For all problems on this homework, prove that your algorithm is correct, and analyse the worst-case complexity of your algorithm.