# CS 61A: Homework 7

Due by 11:59pm on Wednesday, 11/5

Submission: See Lab 1 for submission instructions. We have provided a hw7.scm starter file for the questions below.

Readings: You might find the following references useful:

To complete this homework assignemnt on your own computer, you will either need to install Scheme or use our online Scheme interpreter.

You can load the starter file in STK using the command

``stk -load hw7.scm``

Scheme does not have a built-in testing framework. To verify behavior, we will use the following `assert-equal` procedure, which tests whether an `expression` evaluates to an expected `value`.

``````(define (assert-equal value expression)
(if (equal? value (eval expression))
(print 'ok)
(print (list 'for expression ':
'expected value
'but 'got (eval expression)))))``````

When you evaluate your solution, a long sequence of `ok` should be displayed. Any test failures will describe the error instead.

### Question 1

Define the procedures `cadr` and `caddr`, which return the second and third elements of a list, respectively:

``````(define (cddr s)
(cdr (cdr s)))

nil)

nil)

(assert-equal (list 3 4) '(cddr '(1 2 3 4)))
(assert-equal 2          '(cadr '(1 2 3 4)))
(assert-equal 3          '(caddr '(1 2 3 4))))

### Conditional expressions

The `cond` special form is a general conditional expression, similar to a multi-clause conditional statement in Python. The general form of a conditional expression is:

``````(cond
(<p1> <e1>)
(<p2> <e2>)
...
(<pn> <en>)
(else <else-expression>))``````

consisting of the symbol `cond` followed by pairs of expressions ```(<p> <e>)``` called clauses. The first expression in each pair is a predicate: an expression whose value is interpreted as either `true` or `false`.

Conditional expressions are evaluated as follows. The predicate `<p1>` is evaluated first. If its value is `false`, then `<p2>` is evaluated. If `<p2>`'s value is also `false`, then `<p3>` is evaluated. This process continues until a predicate is found whose value is `true`, in which case the interpreter returns the value of the corresponding consequent expression `<e>` of the clause as the value of the conditional expression. If none of the `<p>`'s is found to be `true`, the interpreter returns the value of the `else` expression.

The word "predicate" is used for procedures that return `true` or `false`, as well as for expressions that evaluate to `true` or `false`.

### Question 2

Using `cond`, define a procedure `sign` that returns `-1` for negative arguments, `0` for zero, and `1` for positive arguments:

``````(define (sign x)
nil)

(define (test-sign)
(assert-equal -1 '(sign -42))
(assert-equal 0  '(sign 0))
(assert-equal 1  '(sign 42)))

(test-sign)``````

### Question 3

Define the procedure `gcd` that uses the Euclidean algorithm to find the greatest common divisor of two positive integers:

``````(define (gcd m n)
nil)

(define (test-gcd)
(assert-equal 4 '(gcd 12 8))
(assert-equal 4 '(gcd 12 16))
(assert-equal 8 '(gcd 16 8))
(assert-equal 6 '(gcd 24 42))
(assert-equal 5 '(gcd 5 5)))

(test-gcd)``````

### Question 4

Implement a procedure `pow` for raising the number `b` to the power of integer `n` that runs in Theta(log n) time. Hint: Use the built-in predicates `even?` and `odd?` and the `square` procedure to implement the procedure using successive squaring, as we did in lecture:

``````(define (square x) (* x x))

(define (pow b n)
nil)

(define (test-pow)
(assert-equal 1024 '(pow 2 10))
(assert-equal 1000 '(pow 10 3))
(assert-equal 243  '(pow 3 5)))

(test-pow)``````

### Question 5

Write the predicate `ordered?`, which takes a list of numbers and returns whether the numbers are in ascending order.

``````(define (ordered? lst)
nil)

(define (test-ordered?)
(assert-equal true  '(ordered? '(1 2 3 4 5)))
(assert-equal false '(ordered? '(1 5 2 4 3))))

(test-ordered?)``````

### Question 6

One way to represent a set is to store the elements in a sorted list that contains no repeated elements. Define a procedure `contains?` that returns whether a set `s` contains value `v`, assuming `s` is represented in this way. The Python implementation of this procedure is provided for your reference.

``````; Sets as sorted lists

(define (empty? s) (null? s))

(define (contains? s v)
(cond ((empty? s) false)
(else nil)
))

; Equivalent Python code, for your reference:
;
; def empty(s):
;     return len(s) == 0
;
; def contains(s, v):
;     if empty(s):
;         return False
;     elif s.first > v:
;         return False
;     elif s.first == v:
;         return True
;     else:
;         return contains(s.rest, v)

(define odds (list 3 5 7 9))

(define (test-contains)
(assert-equal true '(contains? odds 3))
(assert-equal true '(contains? odds 9))
(assert-equal false '(contains? odds 6)))

(test-contains)``````

### Question 7

Next, define `append`, which takes a set `s` and a value `v` as arguments. It returns a representation of a set containing the values in `s` and the value `v`. There should be no repeated elements in the return value.

``````(define (append s v)
(cond ((empty? s) (list v))
(else nil)
))

(define (test-append)
(assert-equal '(2 3 5 7 9)  '(append odds 2))
(assert-equal '(3 5 7 9)    '(append odds 5))
(assert-equal '(3 5 6 7 9)  '(append odds 6))
(assert-equal '(3 5 7 9 10) '(append odds 10)))

(test-append)``````

### Question 8

Next, define `intersect`, which returns a set containing only values that appear in both sets `s` and `t`. Your implementation should run in linear time in the length of the input sets. The Python implementation of this procedure is provided for your reference.

Also, define `union`, which returns a set containing all values that appear in either set `s` or `t`.

``````(define (intersect s t)
(cond ((or (empty? s) (empty? t)) nil)
(else nil)
))

; Equivalent Python code, for your reference:
;
; def intersect(set1, set2):
;     if empty(set1) or empty(set2):
;     else:
;         e1, e2 = set1.first, set2.first
;         if e1 == e2:
;         elif e1 < e2:
;             return intersect(set1.rest, set2)
;         elif e2 < e1:
;             return intersect(set1, set2.rest)

(define eight (list 1 2 3 4 5 6 7 8))

(define (test-intersect)
(assert-equal '(3 5) '(intersect odds (list 2 3 4 5)))
(assert-equal '()    '(intersect odds (list 2 4 6 8)))
(assert-equal '(3 5 7)   '(intersect odds eight)))

(define (union s t)
(cond ((empty? s) t)
((empty? t) s)
(else nil)
))

(define (test-union)
(assert-equal '(2 3 4 5 7 9)       '(union odds (list 2 3 4 5)))
(assert-equal '(2 3 4 5 6 7 8 9)   '(union odds (list 2 4 6 8)))
(assert-equal '(1 2 3 4 5 6 7 8 9) '(union odds eight)))

(test-intersect)
(test-union)``````

### Question 9

Another way to represent a set is to store the elements in a binary search tree. A binary search tree's branches are either empty or binary search trees. Also, the entry at the root of the tree must be greater than all entries in the left branch and less than all entries in the right branch.

The following procedures define a data abstraction for a binary search tree.

``````; A data abstraction for binary trees where nil represents the empty tree
(define (tree entry left right) (list entry left right))
(define (entry t) (car t))
(define (empty? s) (null? s))
(define (leaf entry) (tree entry nil nil))``````

Define the procedure `in?`, which returns whether a binary search tree `t` contains an element `v`. Your implementation should run in logarithmic time in the number of entries in a balanced input tree. The Python implementation of this procedure is provided for your reference.

``````(define (in? t v)
(cond ((empty? t) false)
(else nil)
))

; Equivalent Python code, for your reference:
;
; def contains(s, v):
;     if s.is_empty:
;         return False
;     elif s.entry == v:
;         return True
;     elif s.entry < v:
;         return contains(s.right, v)
;     elif s.entry > v:
;         return contains(s.left, v)

(define odd-tree (tree 3 (leaf 1)
(tree 7 (leaf 5)
(tree 9 nil (leaf 11)))))

(define (test-in?)
(assert-equal true  '(in? odd-tree 1))
(assert-equal false '(in? odd-tree 2))
(assert-equal true  '(in? odd-tree 3))
(assert-equal false '(in? odd-tree 4))
(assert-equal true  '(in? odd-tree 5)))

(test-in?)``````

### Question 10

Define `as-list`, which takes a binary search tree and returns a sorted list containing the entries of the tree. For an optional challenge, define the procedure so that it runs in linear time in the length of the resulting list. Converting to and from the sorted list representation in linear time allows binary search trees to be intersected in linear time.

``````(define (as-list t)