Section 6.4 Huffman Codes
539
22. Our existing binary search algorithm (Chapter 3, Example 13) contains the pseudocode instruction
find the index k midway between i and j
after which the target x is compared to the list item at index k, the “midpoint item.” Suppose that this instruction is replaced by
if i = j then
k = j
else
k = i + 1
end if
a. Draw the decision tree that results from using the modified algorithm on a sorted list with n = 8.
b. Give the exact number of comparisons required (see Exercise 21) in the worst case for n = 8.
c. Give a worst-case order-of-magnitude expression for the number of comparisons required as a function of n, and justify your expression. Comment on the use of this algorithm as opposed to the original
binary search algorithm, which is Θ(log n).
23. To prove that log n! = Θ(n log n), we can use the definition of order of magnitude (see
Section 5 of Chapter 5) and show that there exist positive constants n 0 , c 1 , and c 2 such that for
n ≥ n 0 , c 1 (n log n) ≤ log n! ≤ c 2 (n log n).
a. Show that for n ≥ 1,log n! ≤ n log n. (Hint: Use the definition of n! and properties of logarithms.)
b. Show that for n ≥ 4, log n! ≥ (1͞4)(n log n). (Hint: Use the definition of n! and properties of
logarithms, but stop at log
Problem and Trial Solution
Character data consist of letters of the alphabet (both uppercase and lowercase),
punctuation symbols, and other keyboard symbols such as @ and %. Computers
store character data in binary form, as a sequence of 0s and 1s, usually by fixing
some length n so that 2
n
is at least as large as the number of distinct characters
and then encoding each distinct character as a particular sequence of n bits. Each
character must be encoded into its fixed binary sequence for electronic storage, and
then the binary sequence must be decoded when the character is to be displayed.
The most common encoding scheme for many years was ASCII (American Standard Code for Information Interchange), which uses n = 8, so that each character
requires 8 bits to store. However, 2
8
= 256, so a maximum of 256 characters could
be encoded. This was enough for the English alphabet, punctuation, and special
characters, but as electronic data storage spread around the world, it was not enough
to include characters found in other languages such as Russian, Japanese, Arabic,
Greek, and many others. Unicode (in general) uses 16 bits to encode a single character, so that 2
16
= 65536 character encodings are now available. But whatever
value is chosen for n, each character requires the same amount of storage space.
Suppose a collection of character data to be stored in a file in binary form is
large enough that the amount of storage required is a consideration. Suppose also
that the file is archival in nature, and its contents will not often be changed. Then
539
22. Our existing binary search algorithm (Chapter 3, Example 13) contains the pseudocode instruction
find the index k midway between i and j
after which the target x is compared to the list item at index k, the “midpoint item.” Suppose that this instruction is replaced by
if i = j then
k = j
else
k = i + 1
end if
a. Draw the decision tree that results from using the modified algorithm on a sorted list with n = 8.
b. Give the exact number of comparisons required (see Exercise 21) in the worst case for n = 8.
c. Give a worst-case order-of-magnitude expression for the number of comparisons required as a function of n, and justify your expression. Comment on the use of this algorithm as opposed to the original
binary search algorithm, which is Θ(log n).
23. To prove that log n! = Θ(n log n), we can use the definition of order of magnitude (see
Section 5 of Chapter 5) and show that there exist positive constants n 0 , c 1 , and c 2 such that for
n ≥ n 0 , c 1 (n log n) ≤ log n! ≤ c 2 (n log n).
a. Show that for n ≥ 1,log n! ≤ n log n. (Hint: Use the definition of n! and properties of logarithms.)
b. Show that for n ≥ 4, log n! ≥ (1͞4)(n log n). (Hint: Use the definition of n! and properties of
logarithms, but stop at log
Problem and Trial Solution
Character data consist of letters of the alphabet (both uppercase and lowercase),
punctuation symbols, and other keyboard symbols such as @ and %. Computers
store character data in binary form, as a sequence of 0s and 1s, usually by fixing
some length n so that 2
n
is at least as large as the number of distinct characters
and then encoding each distinct character as a particular sequence of n bits. Each
character must be encoded into its fixed binary sequence for electronic storage, and
then the binary sequence must be decoded when the character is to be displayed.
The most common encoding scheme for many years was ASCII (American Standard Code for Information Interchange), which uses n = 8, so that each character
requires 8 bits to store. However, 2
8
= 256, so a maximum of 256 characters could
be encoded. This was enough for the English alphabet, punctuation, and special
characters, but as electronic data storage spread around the world, it was not enough
to include characters found in other languages such as Russian, Japanese, Arabic,
Greek, and many others. Unicode (in general) uses 16 bits to encode a single character, so that 2
16
= 65536 character encodings are now available. But whatever
value is chosen for n, each character requires the same amount of storage space.
Suppose a collection of character data to be stored in a file in binary form is
large enough that the amount of storage required is a consideration. Suppose also
that the file is archival in nature, and its contents will not often be changed. Then