8. a. Write a program that constructs a Huffman code for a given English
text and encode it.
9. Card guessing Design a strategy that minimizes the expected number of
questions asked in the following game [Gar94]. You have a deck of cards
that consists of one ace of spades, two deuces of spades, three threes,
32
Hints to Exercises 9.4
1. Seetheexamplegiveninthesection.
2. After combining the two nodes with the lowest probabilities, resolve the
tiearisingonthenextiterationintwodifferent ways. For each of the two
Huffman codes obtained, compute the mean and variance of the codeword
length.
5. a. What is the most appropriate data structure for an algorithm whose
principal operation is finding the two smallest elements in a given set,
deleting them, and then adding a new item to the remaining ones?
b. Identify the principal operations of the algorithm, the number of times
they are executed, and their efficiencies for the data structure used.
Solutions to Exercises 9.4
1. a.
0.1
B
0.15
D
0.15
_
0.2
C
0.4
A
0.4
A
0.6
0.25
0.35
34
character ABC D _
probability 0.4 0.1 0.2 0.15 0.15
codeword 0 100 111 101 110
35
2. Here is one way:
0.1
A
0.1
B
0.2
C
0.2
D
0.4
E
0.4
0.6
0.2
0.1
A
0.1
B
0.2
C
0.2
D
0.4
E
36
character ABCDE
probability 0.1 0.1 0.2 0.2 0.4
codeword 1100 1101 111 10 0
length 44321
37
0.4
E
0.2
0.1
A
0.1
B
0.4
0.2
C
0.2
D
1.0
01
0.4
E
0.6
0
1
38
Thus, the mean and variance of the codeword’s length are, respectively,
3. a. Yes. This follows immediately from the way Huffman’s algorithm oper-
ates: after each of its iterations, the two least frequent characters that are
3)(1
3)(1
3))
b. Yes. Let’s use the optimality of Huffman codes to prove this property
by contradiction. Assume that there exists a Huffman code containing
two characters and such that ()()and (()) (())
4. The answer is −1Since two leaves corresponding to the two least fre-
quent characters must be on the same level of the tree, the tallest Huffman
coding tree has to have the remaining leaves each on its own level. The
height of such a tree is −1An easy and natural way to get a Huffman
5. a. The following pseudocode is based on maintaining a priority queue of
trees, with the priorities equal the trees’ weights.
Algorithm Huffman([0 −1])
//Constructs Huffman’s tree
//Input: An array [0 −1] of weights
6. The critical insight here is that the weights of the trees generated by Huff–
man’s algorithm for nonnegative weights (frequencies) form a nondecreas-
ing sequence. As the hint to this problem suggests, we can then maintain
7. Use one of the standard traversals of the binary tree and generate a bit
string for each node of the tree as follows:. Starting with the empty bit
8. We can generate the codewords right to left by the following method that
stems immediately from Huffman’s algorithm: when two trees are com-
9. n/a
41
10. The probabilities of a selected card be of a particular type is given in the
following table:
Huffman’s tree for this data looks as follows:
1/45 2/45 3/45 4/45 5/45 6/45 7/45 8/45 9/45
The first question this tree implies can be phrased as follows: ”Is the se-
lected card a four, a five, or a nine?” . (The other questions can be
phrased in a similar fashion.)
42