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.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s