SICP Exercise 2.72

SICP Exercise 2.72

For the special case in SICP Exercise 2.71, the order of growth for encoding the most frequent symbol is . As for the least frequent symbol, the order of growth is . The most expensive part of the operation is to search the symbol list at each node. The number of steps required for searching an unordered list of m elements is . For the least frequent symbol, we need to go down the tree times and search at every node encountered. Thus the order of growth of the number of steps is .

SICP Exercise 2.71

SICP Exercise 2.71

Encoding the most frequent symbol requires one bit, whereas n-1 bits are required to encode the least frequent symbol.

SICP Exercise 2.70

SICP Exercise 2.70

(define tree
  (generate-huffman-tree '((A 2) (BOOM 1) (GET 2) (JOB 2) 
                           (NA 16) (SHA 3) (YIP 9) (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)
        tree)
;Value: (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)
(length (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)
                tree))
;Value: 84

The encoding requires 84 bits. If we use a fixed-length code, we will need 3 bits per symbol for the 8-symblo alphabet. The song has 36 symbols in total. Thus encoding with the fixed-length code will require 108 bits.

SICP Exercise 2.69

SICP Exercise 2.69

(define (successive-merge tree)
  (if (null? (cdr tree))
      (car tree)
      (let ((node-1 (car tree))
            (node-2 (cadr tree))
            (rest (cddr tree)))
        (let ((new-node (make-code-tree node-1 node-2)))
          (successive-merge (adjoin-set new-node rest))))))

(define pairs '((A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)))
(generate-huffman-tree pairs)
;Value: ((leaf a 8) ((((leaf h 1) (leaf g 1) (h g) 2) ((leaf f 1) (leaf e 1) (f e) 2) (h g f e) 4) (((leaf d 1) (leaf c 1) (d c) 2) (leaf b 3) (d c b) 5) (h g f e d c b) 9) (a h g f e d c b) 17)

SICP Exercise 2.68

SICP Exercise 2.68

(define (encode-symbol sym tree)
  (define (element-of-symbols? x syms)
    (cond ((null? syms) false)
          ((equal? x (car syms)) true)
          (else (element-of-symbols? x (cdr syms)))))
  (define (encode-symbol-1 sym tree result)
    (let* ((left (left-branch tree))
           (left-symbols (symbols left)))
      (if (element-of-symbols? sym left-symbols)
          (if (leaf? left)
              (append result (list 0))
              (encode-symbol-1 sym left (append result (list 0))))
          (let* ((right (right-branch tree))
                 (right-symbols (symbols right)))
            (if (element-of-symbols? sym right-symbols)
                (if (leaf? right)
                    (append result (list 1))
                    (encode-symbol-1 sym right (append result (list 1))))
                (error "unknown symbol:" sym))))))
  (encode-symbol-1 sym tree '()))
              
(encode '(a d a b b c a) sample-tree) 
;Value: (0 1 1 0 0 1 0 1 0 1 1 1 0)

(encode '(a e a b d c) sample-tree)
;unknown symbol: e

SICP Exercise 2.67

SICP Exercise 2.67

The message is (a d a b b c a).

SICP Exercise 2.66

SICP Exercise 2.66

(define (lookup given-key set-of-records)
  (if (null? set-of-records) 
      false
      (let ((record (entry set-of-records)))
        (cond ((= given-key (key record)) record)
              ((< given-key (key record))
               (lookup given-key (left-branch set-of-records)))
              ((> given-key (key record))
               (lookup given-key (right-branch set-of-records)))))))

SICP Exercise 2.65

SICP Exercise 2.65

We use procedures union-set in SICP Exercise 2.62, intersection-set for sets as ordered lists in SICP Section 2.3.3, tree->list-2 in SICP Exercise 2.63, and list->tree in SICP Exercise 2.64. All of them are procedures.

(define (union-set-tree set1 set2)
  (let ((list1 (tree->list-2 set1))
        (list2 (tree->list-2 set2)))
    (list->tree (union-set list1 list2))))

(define (intersection-set-tree set1 set2)
  (let ((list1 (tree->list-2 set1))
        (list2 (tree->list-2 set2)))
    (list->tree (intersection-set list1 list2))))

SICP Exercise 2.64

SICP Exercise 2.64

Procedure partial-tree takes a list and an interger n as arguments. It turns the first n elements of the list into a balanced tree by applying partial-tree to roughly the first and the second halves of the elements to form the left and right branches, making the one element left in the middle an entry for the tree. This process goes on recursively until a tree is formed.

; The tree converted from the list (1 3 5 7 9 11)

                5
              /   \
             /     \
            /       \
           /         \
          1          9
           \        / \
            \      /   \
             3    7    11

The order of growth is .

SICP Exercise 2.63

SICP Exercise 2.63

(define t1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
(tree->list-1 t1)
;Value: (1 3 5 7 9 11)
(tree->list-2 t1)
;Value: (1 3 5 7 9 11)

(define t2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))))
(tree->list-1 t2)
;Value: (1 3 5 7 9 11)
(tree->list-2 t2)
;Value: (1 3 5 7 9 11)

(define t3 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ()))))
(tree->list-1 t3)
;Value: (1 3 5 7 9 11)
(tree->list-2 t3)
;Value: (1 3 5 7 9 11)

The two procedures produce the same results.

Suppose there is a balanced tree with n elements. We know that the depth of the tree is . The deepest level has nodes. To convert the tree into a list using procedure tree->list-1, the number of calls to tree->list-1 is . However, this does not mean the order of growth is because tree->list-1 uses append. To append a list of items to another list of items using append has an order of growth of . Since the tree has a depth of and the number of steps required by append to visit the list items at each level is , we find that procedure tree->list-1 has an order of growth of . As for tree->list-2, it has an order of growth of because it does not have any expensive operations like append.