# SICP 2.3 exercises cont. 4

**Posted:**January 31, 2013

**Filed under:**Improving, SICP Leave a comment

**2.70**

(define (successive-merge elements) (if (null? (cdr elements)) (car elements) (let ((e1 (car elements)) (e2 (cadr elements)) (rest (cddr elements))) (successive-merge (adjoin-set (make-code-tree e1 e2) rest))))) (define song (generate-huffman-tree '((A 2) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (WAH 1)))) (encode '(GET A JOB SHA NA NA NA NA NA NA NA NA GET A JOB SHA NA NA NA NA NA NA NA NA WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP SHA BOOM) song) (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)

84 bits using huffman encoding above.

fixed length encoding would require 3 bit per word for 36 words, which is 108 bits.

**2.71**

Just going to have the diagram for n=5 here, as n=10 looks the same, just longer.

1 bit for the most frequent symbol

n bits for least frequent symbol

**2.72**

Most frequent symbol will be encoded in O(1) time because it is always the first symbol that the encode procedure encounters as shown in 2.71.

The least frequent symbol will be encoded in O(n^2) time because at each level of the tree, encode must scan through up to n symbols to check which branch to encode, and there are n levels in the tree.

**Comments:** Finally done with 2.3. These questions made me realized I implemented encode incorrectly as my answer yesterday raises an error inappropriately. In fact I was overcomplicating it as I had forgotten that parent node has information about what symbols are represented by the branch. Correct answer below.

(define (encode-symbol symbol tree) (cond ((leaf? tree) '()) ((element-of-set? symbol (symbols (left-branch tree))) (cons 0 (encode-symbol symbol (left-branch tree)))) ((element-of-set? symbol (symbols (right-branch tree))) (cons 1 (encode-symbol symbol (right-branch tree)))) (else (error "No such symbol in tree:" symbol))))