Section-2.3.4; Ex-2.67-2.72

Ex 2.67
1 ]=> (decode sample-message sample-tree)
;Value 1: (a d a b b c a)

Ex-2.68

(define (encode-symbol symbol tree)
  (define (iter tree-or-leaf result)
    (cond
     ((leaf? tree-or-leaf)
      (if (eq? symbol (symbol-leaf tree-or-leaf))
          result
          (error "symbol is not in given tree")))
     ((memq symbol (symbols tree-or-leaf))
      (if (memq symbol (symbols (left-branch tree-or-leaf)))
          (iter (left-branch tree-or-leaf) (cons 0 result))
          (iter (right-branch tree-or-leaf) (cons 1 result))))
     (else (error "symbol is not in given tree"))))
  (reverse (iter tree '())))

1 ]=> (encode '(a d a b b c a) sample-tree)
;Value 3: (0 1 1 0 0 1 0 1 0 1 1 1 0)
1 ]=> (equal? (encode '(a d a b b c a)
                      sample-tree)
              sample-message)
;Value: #t 

Ex-2.69

(define (successive-merge leafs)
  (cond
   ((null? leafs) nil)
   ((= (length leafs) 1)
    (make-code-tree (car leafs) nil))
   ((= (length leafs) 2)
    (make-code-tree (cadr leafs) (car leafs)))
   (else
    (successive-merge
     (cons (make-code-tree (cadr leafs) (car leafs))
           (cddr leafs)))))) 

Ex-2.70

(define rock-pairs '((na 16)
                (yip 9)
                (sha 3)
                (job 2)
                (get 2)
                (a 2)
                (boom 1)
                (wah 1)))
(define encoded-message
  (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)
   (generate-huffman-tree rock-pairs)))

;number of bits used
1 ]=> (length encoded-message)
;Value: 87 

For fixed length encoding:
there are 8 distinct symbols, so we need atleast 3 bits for each symbol, and message has 36 symbols, so for fixed-length code we would need
3 X 36 = 108 bits

Ex-2.71
For most frequent symbol we need just 1 bit for any value of n.
For least frequent symbol:
number of bits needed =
depth of the generated tree =
(ceiling (log n)) ;where base=2 in log

Ex-2.72 - todo