Search This Blog

Tuesday, March 24, 2009

Exercise 16.3.5 - Introduction to Algorithms

Suppose we have an optimal prefix code on a set C = {0, 1, ..., n - 1} of characters and we wish to transmit this code using as few bits as possible. Show how to represent any optimal prefix code on C using only 2n - 1 + n ⌈lg n⌉ bits. (Hint: Use 2n - 1 bits to specify the structure of the tree, as discovered by a walk of the tree.)

Sol.

No comments:

Post a Comment

Blog Archive