HOMEWORK 8

Background: Ch. 24.1, 24.2, 25.1, 31.1, 16.3.

Due December 10th (optional):

• 8.1: Given a graph G=(E,V), let e be the second smallest edge in G according to the weight function w. Argue that there is an MST containing e. You can assume there are no ties in the weight function (all weights are unique).

• 8.2: Give an example of a graph for which the shortest-path tree and the minimum spanning tree are different.

• 8.3: Let's say you are throwing a party. Your house is a node in a directed graph. Explain how you'd use an algorithm for single-source shortest paths to compute directions for all the other nodes of the graph. That is, solve the single-destination shortest path problem and compute a different kind of shortest-path tree.

• 8.4: CLR Exercise 34.1-3 (pg. 856).

• 8.5: Use the properties of matrix multiplication to argue that, for any matrix A, A^T A is a well-defined matrix product and that it is symmetric.

• 8.6: Modify MAXPROB to print the most likely sequence of words. Give the running time for this operation.

• 8.7: CLR Exercise 16.3-5 (pg. 319).