Chapter 16 Answers

Greedy Overview

Question 16.1

• Starting at vertex 100, apply a greedy search using the heuristic: "choose the largest adjacent vertex, stop if all are smaller" to find the maximum 3-bit value on the upper-right figure. Follows path <100, 110, 111>
• Did a locally optimal choice lead to a globally optimal solution? Yes.
• Try your method on the figure below starting at vertex 001. Follows path <001, 101>
• Did a locally optimal choice lead to a globally optimal solution? No.
• Does this problem have the greedy-choice property (a globally optimal solution can be arrived at by making locally optimal (greedy) choice)? No.

Example: Huffman codes for optimal data compression

For example, consider the following sentence:

dead beef cafe deeded dad.  dad faced a faded cab.  dad acceded.  dad be bad.

Frequencies for the 77 characters are:

a	b	c	d	e	f		.
12	4	5	19	12	4	17	4

Question 16.2 - Which characters should we encode in the fewest bits? The characters occurring most frequently should be encoded with the fewest number of bits.

Constructing a Huffman code

Question 16.3 - In above Figure (b), why are codes for a=0 and f=1100? a is left. f is right, right, left, left.

Question 16.4 Where's the greed? Always extract two lowest frequency values from a character frequency min-heap, place (minimum) remaining at lower (longer code) levels of code tree.