my attempt to do the exercises in sicp.

Tuesday, July 29, 2008

sicp exercise 2.71

;; Exercise 2.71.  Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., 2^n-1. Sketch the tree for n=5; for n=10. In such a tree (for general n) how may bits are required to encode the most frequent symbol? the least frequent symbol?

;; huffman tree for n=5 (below)

;; huffman tree for n=10 is also similar.

;; bits to encode most frequent symbol = n-1
;; bits to encode least frequent symbol = 1

No comments: