Chapter 11: Trees

construct a Huffman code for the letters of the English alphabet where the frequencies of letters in typical English text are as shown in this table.

Frequency Letter

Suppose that \({\bf{m}}\) is a positive integer with \({\bf{m}} \ge {\bf{2}}\). An m-ray Huffman code for a set of \({\bf{N}}\) symbols can be constructed analogously to the construction of a binary Huffman code. At the initial step, \(\left( {\left( {{\bf{N - 1}}} \right){\bf{ mod }}\left( {{\bf{m - 1}}} \right)} \right){\bf{ + 1}}\) trees consisting of a

single vertex with least weights is combined into a rooted tree with these vertices as leaves. At each subsequent step ,the \({\bf{m}}\) trees of least weight are combined into an m-ray tree.

Prove that Sollin’s algorithm produces a minimum spanning tree in a connected undirected weighted graph.

Which of these graphs are cacti?

How many vertices and how many leaves does a complete \({\bf{m - }}\)ary tree of height \(h\) have?

Use backtracking to find a subset, if it exists, of the set {27, 24, 19, 14, 11, 8} with sum

a) 20. b) 41. c) 60.

Describe the m-aryx Huffman coding algorithm in pseudocode.

Show that the first step of Sollin’s algorithm produces a forest containing at least \(\left\lceil {\frac{n}{2}} \right\rceil \) edges when the input isan undirected graph with \(n\) vertices.

Show that preorder traversals of the two ordered rooted trees displayed below produce the same list of vertices. Note that this does not contradict the statement in Exercise 26, because the numbers of children of internal vertices in the two ordered rooted trees differ.

Is a tree necessarily a cactus?

Prove

\({\bf{a)}}\)part \(\left( {ii} \right)\) of Theorem \(4\).

\({\bf{b)}}\)part \(\left( {{\bf{iii}}} \right)\) of Theorem \(4\).