CS 37
Clab 11: Binary Search Trees (BST) and a peek at complex numbers
Below are solutions to ex 2.59 and 2.61 from last clab.
Now, do the following exercises for BSTs and sets implemented
by them.
- exercise 2.63 on page 158
- exercise 2.64 on page 159
They are a couple screens down from:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_sec_2.3.3
Here are the three trees from Figure 2.16.
<![CDATA[
(define tre1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
(define tre2 '(3 (1 () ()) (7 (5 () ())(9 () (11 () ())))))
(define tre3 '(5 (3 (1 () () ) ()) (9 (7 () ()) (11 () ()))))
]]>
Here is code from pages 155-159
<![CDATA[
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
(list entry left right))
(define (element-of-set? x set)
(cond ((null? set) #f)
((= x (entry set)) #t)
((< x (entry set))
(element-of-set? x (left-branch set)))
((> x (entry set))
(element-of-set? x (right-branch set)))))
(define (adjoin-set x set)
(cond ((null? set) (make-tree x '() '()))
((= x (entry set)) set)
((< x (entry set))
(make-tree (entry set)
(adjoin-set x (left-branch set))
(right-branch set)))
((> x (entry set))
(make-tree (entry set)
(left-branch set)
(adjoin-set x (right-branch set))))))
;; EXERCISE 2.63
(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))
;; EXERCISE 2.64
(define (list->tree elements)
(car (partial-tree elements (length elements))))
(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))))))))
]]>
ask any questions you may have.
I'll say a few words about complex numbers. Then we'll work through
some of the material on pp. 169-175.
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-17.html#%_sec_2.4
Here is some code to add and multiply complex numbers given
in rectangular form. Also a couple of complex numbers and
a definition of pi.
<![CDATA[
(define (make-from-real-imag x y) (cons x y))
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (add-complex z1 z2)
(make-from-real-imag (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2))))
(define (mul-complex2 z1 z2)
(make-from-real-imag (-
(* (real-part z1) (real-part z2))
(* (imag-part z1) (imag-part z2)))
(+
(* (real-part z1) (imag-part z2))
(* (imag-part z1) (real-part z2)))))
(define cpx45 (make-from-real-imag 4 4))
(define cpx30 (make-from-real-imag (sqrt 3) 1))
(define cpx60 (make-from-real-imag 2 (* 2 (sqrt 3))))
(define pi (* 2 (asin 1)))
]]>
now we'll add more from section 2.4.1
<![CDATA[
(define (sub-complex z1 z2)
(make-from-real-imag (- (real-part z1) (real-part z2))
(- (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
(make-from-mag-ang (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
(make-from-mag-ang (/ (magnitude z1) (magnitude z2))
(- (angle z1) (angle z2))))
]]>
add and subtract will work with rectangular form mul and div
need polar form so Ben needs conversion functions
<![CDATA[
(define (square x) (* x x))
(define (magnitude z)
(sqrt (+ (square (real-part z)) (square (imag-part z)))))
(define (angle z)
(atan (imag-part z) (real-part z)))
(define (make-from-mag-ang r a)
(cons (* r (cos a)) (* r (sin a))))
]]>
Let's try Bens functions
Don't close Ben's window. But open a new window for Alyssa and put
the following in her window.
<![CDATA[
;; the same implementation independent definitions of
;; add, sub, mult, div
(define (add-complex z1 z2)
(make-from-real-imag (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2))))
(define (sub-complex z1 z2)
(make-from-real-imag (- (real-part z1) (real-part z2))
(- (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
(make-from-mag-ang (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
(make-from-mag-ang (/ (magnitude z1) (magnitude z2))
(- (angle z1) (angle z2))))
;; add and subtract will work with rectangular form
;; mul and div need polar form so Alyssa also needs conversion
;; functions
(define (square x) (* x x))
;; these functions differ from Ben's functions of same name
(define (real-part z)
(* (magnitude z) (cos (angle z))))
(define (imag-part z)
(* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y)
(cons (sqrt (+ (square x) (square y)))
(atan y x)))
(define (make-from-mag-ang r a) (cons r a))
;; try a couple of Alyssa's functions
(define acpx30 (make-from-real-imag 1.7320508075688772 1))
(define acpx45 (make-from-real-imag 4 4))
(define acpx60 (make-from-real-imag 2 3.4641016151377544))
]]>
Let's try a couple of Alyssa's functions on numbers in polar form.
Solutions from last clab.
<![CDATA[
;; couple of test sets
(define x '(cat rat mat))
(define y '(1 4 9 16))
;; essentially same as text p. 154 except works for elements that
;; are not numbers
(define (eltof? el set) ;;; returns #t if el is an element of set set
;;; returns #f otherwise
(cond
((null? set) #f)
((equal? el (car set)) #t)
(else (eltof? el (cdr set)))
)
)
;;;ex 2.59 by charles kelemen
;;; union returns the unordered list representation of the
;;; union of the two sets set1 and set2
(define (union set1 set2)
(if (null? set1) ;;; if set1 is empty the union is
set2 ;;; just set2
(let ((eltof1 (car set1))) ;;; otherwise let eltof1 be the
;;; first element in set1
(if (eltof? eltof1 set2) ;;; if eltof1 is in set2, we can
(union (cdr set1) set2) ;;; union the rest of set1 to set2
;;; otherwise we call union with the rest of set1
;;; as first parameter and eltof1 put into the 2nd param
(union (cdr set1) (cons eltof1 set2))
)
)
)
)
;; for NUMBERS only
;;;ex 2.61 by charles kelemen
;;; assumes that set (2nd parameter) is a set of numbers represented
;;; by a list of its elements in ascending order
(define (ordadjoin el set)
(cond
((null? set) (list el))
(else
(let ((first (car set)))
(cond
((< el first) (cons el set))
((= el first) set)
(else (cons first (ordadjoin el (cdr set))))
)
)
)
)
)
;================================================================
;Some tests.
;:
;ordadjoin
;
;:(ordadjoin 5 y)
;(1 4 5 9 16)
;
;: (ordadjoin 100 y)
;(1 4 9 16 100)
;
;: (ordadjoin -32 y)
;(-32 1 4 9 16)
;
;: (ordadjoin 16 y)
;(1 4 9 16)
;
;================================================================
;
;More Comparing ordadjoin to adjoin (unordered lists)
;must be done with care. The unordered adjoin only requires one cons
;because we can just stick the new element in front once we discover
;that it is really new. The difference is that adjoin calls eltof?
;which must cdr through the whole list in the unordered case. So
;let's compare them by counting cdrs. You can do this empirically
;by tracing cdr in both kinds of adjoin. And then running a number
;of tests.
;
;Exact behavior depends on whether the new element will be early or
;late after insertion into the ordeered set.
;Assuming that you are adjoining a new element that
;belongs in the middle of the ordered set, ordadjoin is about twice as fast
;as the unordered adjoin.
;
;================================================================
]]>
ask any questions you may have.