SICP 2.4 exercises cont.

2.73
c)

(define (install-deriv-package)
  (define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))
  (define (addend s) (car s))
  (define (augend s) (cadr s))
  (define (sum exp var)
    (make-sum (deriv (addend exp) var)
              (deriv (augend exp) var)))

  (define (multiplier p) (car p))
  (define (multiplicand p) (cadr p))
  (define (product exp var)
    (make-sum
     (make-product (multiplier exp)
                   (deriv (multiplicand exp) var))
     (make-product (deriv (multiplier exp) var)
                   (multiplicand exp))))
  (put 'deriv '+ sum)
  (put 'deriv '* product))

d)

Simply change the put arguments:

(put '+ 'deriv sum)
(put '* 'deriv product)
(put '** 'deriv exponentiation)

Spent most of my time learning ruby on rails today, but I got the second half of the problem done.

Advertisements

SICP 2.4 exercises

2.73

a) The dispatch is based on the operator symbol, and when the expression is a single number or a variable, there is no operator to identify. In general, the general procedure tests is the expression is a number or variable and deals with it accordingly. If there is an operator, then the operator symbol is used to retrieve the procedure needed to deal with the expression.

b)

(define (install-deriv-package)
  (define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))
  (define (addend s) (car s))
  (define (augend s) (cadr s))
  (define (sum exp var)
    (make-sum (deriv (addend exp) var)
              (deriv (augend exp) var)))

  (define (multiplier p) (car p))
  (define (multiplicand p) (cadr p))
  (define (product exp var)
    (make-sum
     (make-product (multiplier exp)
                   (deriv (multiplicand exp) var))
     (make-product (deriv (multiplier exp) var)
                   (multiplicand exp))))
  (put 'deriv '+ sum)
  (put 'deriv '* product))

Really busy these days, so this is a record low rate of progress… 1/2 of a problem! Although b) is a decently large problem in itself. Weekend starts though so hopefully I can blast through the problems in the next couple days.


SICP 2.3 exercises cont. 4

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.

huffman

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))))

SICP 2.3 exercises cont. 3

2.67

(decode sample-message sample-tree)
(A D A B B C A)

2.68

(define (encode-symbol symbol tree)
  (if (leaf? tree)
      (if (eq? (symbol-leaf tree) symbol)
          '()
          #f)
    (let ((left-result (encode-symbol symbol (left-branch tree))))
      (if left-result
          (cons 0 left-result)
        (let ((right-result (encode-symbol symbol (right-branch tree))))
          (if right-result
              (cons 1 right-result)
            (error "No such symbol in tree:" symbol)))))))

(encode '(A D A B B C A) sample-tree)
(0 1 1 0 0 1 0 1 0 1 1 1 0)

Snail’s pace now due to school. Oh well, as long as it’s consistent.


SICP 2.3 exercises cont. 2

2.63
a) They both returns lists where the elements are in order, so they always return the same thing.
b) tree->list-2 calls itself n times, once for each element. But each time it does this it also calls append, which will call cons on half of the elements of the current tree referenced by tree-list-2. The result is O(n log n) complexity. On the other hand, tree->list-2 simply calls cons once for each element so it it O(n).

2.64,
a) partial-tree splits the list into 3 parts. The element to be added, all the elements before and all the elements after. make-tree is called on these arguments and recursively on each side. Balance is maintained by making the before and after sections equal length as much as possible.

b) O(n) because make-tree, which has constant cost, is called once per element.

2.65

(define (union-set set1 set2)
  (define (union-list list1 list2)
    (cond ((null? list1) list2)
          ((null? list2) list1)
          (else (let ((x1 (car list1)) (x2 (car list2)))
                  (cond ((= x1 x2)
                         (cons x1 (union-list (cdr list1) (cdr list2))))
                        (( x1 x2)
                         (cons x2 (union-list list1 (cdr list2)))))))))
  (let ((set1-list (tree->list-2 set1))
        (set2-list (tree->list-2 set2)))
    (list->tree (union-list set1-list set2-list))))

(define (intersection-set set1 set2)
  (define (intersection-list list1 list2)
    (if (or (null? list1) (null? list2))
        '()
      (let ((x1 (car list1)) (x2 (car list2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-list (cdr list1)
                                       (cdr list2))))
              ((< x1 x2)
               (intersection-list (cdr list1) list2))
              ((list-2 set1))
        (set2-list (tree->list-2 set2)))
    (list->tree (intersection-list set1-list set2-list))))

I use the O(n) procedures from earlier exercises and examples and simply call them one after another, which results in O(4n) complexity which is O(n).


Comments:
These exercises gave me a lot of practice analyzing complexity and reading code.

2.66

(define (make-entry key record)
  (cons key record))

(define (key entry)
  (car entry))

(define (record entry)
  (cdr entry))

(define (lookup given-key set-of-records)
  (if (null? set-of-records)
      #f
    (let ((k (key (entry set-of-records))))
      (cond ((equal? given-key k)
             (record (entry set-of-records)))
            ((< given-key (key (entry set-of-records)))
             (lookup given-key (left-branch set-of-records)))
            (else
             (lookup given-key (right-branch set-of-records)))))))

What was kind of cool was how easy this was to write once I had definitions for key and entry.

Comments: Didn’t get through that much today. I had been hoping to finish 2.3 today, but I guess it will take one more day.


SICP 2.3 exercises cont.

2.58

Part A is easy.

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list  m1 '* m2))))

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

(define (addend s) (car s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))

(define (multiplier p) (car p))

(define (multiplicand p) (caddr p))

Part B took me a good chunk of the day to get right.

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        ((product? m1) (append m1 (cons '* m2)))
        ((product? m2) (append (list m1 '*) m2))
        (else (list  m1 '* m2))))

(define (simplify e)
  (if (null? (cdr e)) (car e) e))

(define (sum? x)
  (if (and (pair? x) (not (null? (cdr x))))
      (or (eq? (cadr x) '+) (sum? (cddr x)))
    #f))

(define (addend s)
  (if (product? s)
      (make-product (car s) (addend (cddr s)))
      (car s)))

(define (augend s)
  (if (product? s)
      (augend (cddr s))
      (simplify (cddr s))))

(define (product? x)
  (if (and (pair? x) (not (null? (cdr x))))
    (eq? (cadr x) '*)
    #f))

(define (multiplier p) (car p))

(define (multiplicand p)
  (simplify (cddr p)))

I half cheated by looking here, but actually the last part is not good enough as it doesn’t handle precedence. Meanwhile the scheme wiki has some complex looking solutions which I couldn’t be bothered to read properly. In the end, I went with some recursive definitions for the addition selectors and predicates which is easier to understand (to me, anyway) and works, at least for the examples I’ve tested.

(deriv '((3 + 4) * x * y + 4 * z + x) 'x)
(((3 + 4) * y) + 1)

(deriv '(3 * x * y * z + 6 * x * c) 'x)
((3 * y * z) + (6 * c))

2.59

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2) (union-set (cdr set1) set2))
        (else (cons (car set1) (union-set (cdr set1) set2)))))

2.60

(define (adjoin-set x set)
  (cons x set))

(define (union-set set1 set2)
  (append set1 set2))

element-of? and intersection-set are the same as before. The result is faster union and adjoin operations, but slower membership and intersection operations, so this representation would be preferred where sets grow frequently.

2.61

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((= x (car set)) set)
        ((< x (car set)) (cons x set))
        (else (cons (car set) (adjoin-set x (cdr set))))))

2.62

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (let ((x1 (car set1)) (x2 (car set2)))
                (cond ((= x1 x2)
                       (cons x1 (union-set (cdr set1) (cdr set2))))
                      (( x1 x2)
                       (cons x2 (union-set set1 (cdr set2)))))))))

SICP 2.3 exercises

2.53
(list ‘a ‘b ‘c)
(a b c)

(list (list ‘george))
((george))

(cdr ‘((x1 x2) (y1 y2)))
((y1 y2))

(cadr ‘((x1 x2) (y1 y2)))
(y1 y2)

(pair? (car ‘(a short list)))
#f

(memq ‘red ‘((red shoes) (blue socks)))
#f

(memq ‘red ‘(red shoes blue socks))
(red shoes blue socks)

2.54

(define (equal?-2 a b)
  (if (and (or (null? a) (not (pair? a)))
           (or (null? b) (not (pair? b))))
      (eq? a b)
    (if (and (pair? a) (pair? b))
        (and (equal?-2 (car a) (car b))
             (equal?-2 (cdr a) (cdr b)))
      #f)))

2.55
‘something is synctactic sugar for (quote something). Therefore ”abracadabra also means (quote (quote abracadabra)) which is (quote abracadabra). Finally, (car (quote abracadabra)) is quote.

2.56

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ((exponentiation? exp)
         (make-product (exponent exp)
                       (make-exponentiation (base exp)
                                            (make-sum (exponent exp) -1))))
        (else
         (error "unknown expression type -- DERIV" exp))))

(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))

(define (base exp)
  (cadr exp))

(define (exponent exp)
  (caddr exp))

(define (make-exponentiation b e)
  (cond ((=number? e 0) 1)
        ((=number? e 1) b)
        (else (list '** b e))))

Trivial, which is the point of this exercise. The one catch is to remember to use make-sum instead of ‘-‘ in deriv so that it can handle variable exponents.

(define (augend s)
  (if (null? (cdddr s))
      (caddr s)
    (make-sum (caddr s) (cadddr s))))

(define (multiplicand s)
  (if (null? (cdddr s))
      (caddr s)
    (make-product (caddr s) (cadddr s))))

Not so trivial. The difficulty was figuring out which procedures needed to be changed. I personally had a lot of trouble coming to the correct conclusion.