1. Suppose we want to nd the minimum spanning tree of the graph above.
(a) Suppose Prim's algorithm is run on this graph; whenever there is a choice of nodes, always use alphabetic ordering (i.e., V 1 to V 9, then V A; V B; V C). In what order are the edges added to MST?
(b) Suppose Kruskal's algorithm is run on the same graph. Edges of same length are ordered alphabetically. In what order are the edges added to MST?
2. Show how to nd the maximum spanning tree of a graph, that is, the spanning tree of largest total weight.
3. Given two sets A and B, each containing n positive integers, your goal is to reorder the value in each set such that
is maximized, where ai and bi are the i-th value in each set after reordering. Design a greedy algorithm and show that it is optimal.
4. A long string consists of the six characters A, B, D, D, E, F; they appear with frequency 14%, 6%, 19%, 17%, 21%, and 23%, respectively.
(a) Draw the Hu man encoding tree of these six characters.
(b) What is the Hu man encoding of these six characters?
(c) If this encoding is applied to a string consisting of 1,000,000 characters with the given frequencies, what is the length of the encoded string in bits?