*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:

- Question 1
- Conditional expressions
- Question 2
- Question 3
- Question 4
- Question 5
- Question 6
- Question 7
- Question 8
- Question 9
- Question 10

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.

Define the procedures `cadr`

and `caddr`

, which return the second
and third elements of a list, respectively:

```
(define (cddr s)
(cdr (cdr s)))
(define (cadr s)
; YOUR CODE HERE
nil)
(define (caddr s)
; YOUR CODE HERE
nil)
(define (test-car-cadr)
(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))))
(test-car-cadr)
```

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`

.

Using `cond`

, define a procedure `sign`

that returns `-1`

for negative
arguments, `0`

for zero, and `1`

for positive arguments:

```
(define (sign x)
; YOUR CODE HERE
nil)
(define (test-sign)
(assert-equal -1 '(sign -42))
(assert-equal 0 '(sign 0))
(assert-equal 1 '(sign 42)))
(test-sign)
```

Define the procedure `gcd`

that uses the
Euclidean algorithm
to find the greatest common divisor of two positive integers:

```
(define (gcd m n)
; YOUR CODE HERE
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)
```

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)
; YOUR CODE HERE
nil)
(define (test-pow)
(assert-equal 1024 '(pow 2 10))
(assert-equal 1000 '(pow 10 3))
(assert-equal 243 '(pow 3 5)))
(test-pow)
```

Write the predicate `ordered?`

, which takes a list of numbers and
returns whether the numbers are in ascending order.

```
(define (ordered? lst)
; YOUR CODE HERE
nil)
(define (test-ordered?)
(assert-equal true '(ordered? '(1 2 3 4 5)))
(assert-equal false '(ordered? '(1 5 2 4 3))))
(test-ordered?)
```

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)
; YOUR CODE HERE
(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)
```

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))
; YOUR CODE HERE
(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)
```

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)
; YOUR CODE HERE
(else nil)
))
; Equivalent Python code, for your reference:
;
; def intersect(set1, set2):
; if empty(set1) or empty(set2):
; return Link.empty
; else:
; e1, e2 = set1.first, set2.first
; if e1 == e2:
; return Link(e1, intersect(set1.rest, set2.rest))
; 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)
; YOUR CODE HERE
(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)
```

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 (left t) (cadr t))
(define (right t) (caddr 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)
; YOUR CODE HERE
(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?)
```

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)
; YOUR CODE HERE
nil
)
(define (test-as-list)
(assert-equal '(5 7 9 11) '(as-list (right odd-tree)))
(assert-equal '(1 3 5 7 9 11) '(as-list odd-tree)))
(test-as-list)
```