# Homework 7 Solutions

## Solution Files

### Hinting

Homework 7 includes a hinting sytem that generates hints
specifically for your submitted code. If you ever find yourself stuck, you can
ask for hints by using adding the `--hint`

flag to the ok command.

```
$ python3 ok -q pow --hint
...
Hint: There are extra parentheses on line ...
```

The system tries to generate hints specific to your program by applying multiple techniques, including:

- simple pattern matching
- program verification
- program synthesis

### 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)))
(define (cadr s)
(car (cdr s)))
(define (caddr s)
(car (cddr s)))
```

Use OK to unlock and test your code:

```
python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr
```

### 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> <el1>)
(<p2> <el2>)
...
(<pn> <eln>)
(else <else-expressions>))
```

consisting of the symbol `cond`

followed by sequences of expressions ```
(<p>
<el>)
```

called *clauses*. The first expression in each pair is a
*predicate*: an expression whose value is interpreted as either being true
or false. In Scheme, *all* values except the special boolean value `#f`

are
interpreted as true values (unlike Python). (Our particular version of the
Scheme interpreter allows you to write `True`

and `False`

in place of
`#t`

and `#f`

, and prints boolean values as `True`

and `False`

. This is not
standard.)

Conditional expressions are evaluated as follows. The predicate `<p1>`

is evaluated first. If its value is `#f`

,
then `<p2>`

is evaluated.
If `<p2>`

's value is also `#f`

, then `<p3>`

is evaluated. This
process continues until the first predicate `<pi>`

is found whose value is true, in
which case the interpreter returns the result of evaluating each of the
corresponding list of consequent expressions `<eli>`

and returning the last
value as the value of the
whole conditional expression. The `else`

keyword, if present, is taken to be
true, so that if none of the `<p>`

's is found to be true,
the interpreter evaluates the `else-expressions`

and returns the last value.
If no clause has a true predicate, the result is
an "unspecified value". Unless some of the consequent expressions have
side-effects, there is no point in having more than one in a list `<eli>`

.

This is a somewhat simplified version of the semantics of `cond`

, covering the
cases we usually encounter.

### 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)
(cond ((> x 0) 1)
((= x 0) 0)
((< x 0) -1)))
```

Use OK to unlock and test your code:

```
python3 ok -q sign -u
python3 ok -q sign
```

### Question 3: Pow

Implement a procedure `pow`

for raising the number `b`

to the power of a nonnegative integer
`n`

that runs in Θ(log n) time.

Hint:Consider the following observations:

- b
^{2k}= (b^{k})^{2}- b
^{2k+1}= b(b^{k})^{2}You may use the built-in predicates

`even?`

and`odd?`

.

```
(define (square x) (* x x))
(define (pow b n)
(cond ((= n 0) 1)
((even? n) (square (pow b (/ n 2))))
(else (* b (pow b (- n 1))))))
```

Use OK to unlock and test your code:

```
python3 ok -q pow -u
python3 ok -q pow
```

### Question 4

Implement a procedure called `ordered?`

, which takes a list of numbers and
returns `True`

if the numbers are in nondescending order, and `False`

otherwise.

Hint: The built-in`null?`

function returns whether its argument is`nil`

.

```
(define (ordered? s)
(if (or (null? s) (null? (cdr s)))
true
(and (<= (car s) (cadr s)) (ordered? (cdr s)))))
```

Use OK to unlock and test your code:

```
python3 ok -q ordered -u
python3 ok -q ordered
```

### Question 5

Implement the procedure `nodots`

, which takes a nested list of numbers that
may not be well-formed and returns a nested list with the same content and
structure, but which does not have any dots when displayed. Lists are not
well-formed if they do not properly terminate in a null list. In such cases,
the list will print with a dot before the final item to indicate that its
last two items are contained in a single pair. For example,

`(cons 1 (cons 2 3))`

would print as

`(1 2 . 3)`

for which `nodots`

should substitute

`(1 2 3)`

You may find the built-in

`null?`

and`pair?`

predicates useful.

```
(define (nodots s)
(define (dotted s) (and (pair? s)
(not (or (pair? (cdr s))
(null? (cdr s))))))
(cond ((null? s) s)
((dotted s) (list (nodots (car s)) (cdr s)))
((pair? s) (cons (nodots (car s)) (nodots (cdr s))))
(else s)))
```

Use OK to unlock and test your code:

```
python3 ok -q nodots -u
python3 ok -q nodots
```

### Sets as Ordered Lists

One way to represent a set is by using an ordered list, where the ordering is used to speed up search (although only by a constant factor). The following few questions explore this idea, assuming a "set" is a Scheme list with no repeated elements that is already ordered from least to greatest.

### Question 6

Define `contains?`

, which returns whether a set `s`

contains value `v`

. 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)
((> (car s) v) false)
((= (car s) v) true)
((< (car s) v) (contains? (cdr s) v)) ))
; Equivalent Python code, for your reference:
;
; def empty(s):
; return s is Link.empty
;
; 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)
```

Use OK to unlock and test your code:

```
python3 ok -q contains -u
python3 ok -q contains
```

### Question 7

Define `add`

, 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 (add s v)
(cond ((empty? s) (list v))
((= (car s) v) s)
((> (car s) v) (cons v s))
((< (car s) v) (cons (car s) (add (cdr s) v))) ))
```

Use OK to unlock and test your code:

```
python3 ok -q add -u
python3 ok -q add
```

### Question 8

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. A 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)
((= (car s) (car t)) (cons (car s) (intersect (cdr s) (cdr t))))
((< (car s) (car t)) (intersect (cdr s) t))
((> (car s) (car t)) (intersect s (cdr t))) ))
; 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 (union s t)
(cond ((empty? s) t)
((empty? t) s)
((= (car s) (car t)) (cons (car s) (union (cdr s) (cdr t))))
((< (car s) (car t)) (cons (car s) (union (cdr s) t)))
((> (car s) (car t)) (cons (car t) (union s (cdr t)))) ))
```

Use OK to unlock and test your code:

```
python3 ok -q intersect -u
python3 ok -q intersect
python3 ok -q union -u
python3 ok -q union
```

### Question 9: Survey

Please fill out the midsemester survey. You will receive a passphrase after finishing the survey to submit with the homework.

```
(define (survey)
'passphrase-here
)
```

Use OK to unlock and test your code:

```
python3 ok -q survey -u
python3 ok -q survey
```