Hint for question 1: the goal is to count trees, but it turns out to be easier to count sequences. These two things will be equivalent if only we can show that the algorithm given in the question can be reversed.
In question 2, it makes more sense to assume the graph is directed. (Otherwise every edge is both incoming and outgoing.)
In question 3, the running time requested is large enough to first run any of the three minimum spanning tree algorithms we've discussed in class, so you may as well assume that the optimal tree is given at the beginning of your algorithm without increasing the overal running time.
Question 6 is an example of something we'll study later in the course, where we will be able to relate a maximization and a minimization problem by studying their structure.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment