# Homework 7 Solutions

## Solution Files

### Q0: Survey

Before you get started writing code, please fill out the midterm survey.

#### Important Submission Note

You're not done yet!Add the passphrase you receive at the end of the survey to passphrase at the top of the homework. For example, if the passphrase was`CS61A`

(it isn't ðŸ™‚), then the first line of your file should read:

`passphrase = 'CS61A'`

Instead of:

`passphrase = '*** PASSPHRASE HERE ***'`

Use Ok to test your code:

`python3 ok -q survey`

### Q1: Cadr and Caddr

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)))
```

Following the given example of `cddr`

, defining `cadr`

and `caddr`

should be
fairly straightforward.

Just for fun, if this were a Python linked list question instead, the solution might look something like this:

```
cadr = lambda l: l.rest.first
caddr = lambda l: l.rest.rest.first
```

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>))
```

This consists 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 `False`

(historically
called `#f`

) are interpreted as true values. There is also a boolean value
`True`

(historically called `#t`

). In the 61A Scheme interpreter, `False`

and
`#f`

can be used interchangeably.

Conditional expressions are evaluated as follows:

- The predicates
`<p1>`

,`<p2>`

, ...,`<pn>`

are evaluated in that order until one of them evaluates to a true value (anything but`False`

). - If some predicate, such as
`<p2>`

, evaluates to a true value, then the following sequence of consequent expressions, such as`<el2>`

, is evaluated, and its final expression provides the value of the whole`cond`

expression. - Otherwise, if an
`else`

clause is present, then the sequence of`else-expressions`

is evaluated, and its final expression provides the value of the whole`cond`

expression. - If no clause has a true predicate and there is no
`else`

clause, then the value of the`cond`

is unspecified and should not be used.

### Q2: Sign

Using a `cond`

expression, define a procedure `sign`

that takes in one
parameter `x`

and returns -1 if `x`

is negative, 0 if `x`

is zero, and 1 if `x`

is positive.

```
(define (sign x)
(cond ((> x 0) 1)
((= x 0) 0)
((< x 0) -1)))
```

The order of the cases doesn't really matter, and we could also use an `else`

clause in the place of one of the conditions.

The condition looks something like this in Python:

```
if x > 0:
return 1
elif x == 0:
return 0
elif x < 0:
return -1
```

Opinions differ on which is better, but hopefully you can see that the Scheme
`cond`

is quite readable and compact once you get used to it.

Use Ok to unlock and test your code:

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

### Q3: 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
```

The `else`

clause shows the basic recursive version of `pow`

that we've seen
before in class.

We save time in computation by avoiding an extra n/2 multiplications of the
base. Instead, we just square the result of `b^(n/2)`

. This behaviour is what
gives us Î˜(log n) time performance.

Video walkthrough: https://youtu.be/-yt2EOv9ZLU

### Q4: Ordered

Implement a procedure called `ordered?`

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

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

otherwise. Numbers are considered nondescending if each subsequent number is
either larger or equal to the previous, that is:

`1 2 3 3 4`

Is nondescending, but:

`1 2 3 3 2`

Is not.

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)))))
```

We approach this much like a standard Python linked list problem.

- The base case is where
`s`

has zero or one items. Trivially, this is ordered. - Otherwise we check if the first element is in order -- that is, if it's
smaller than the second element. If it's not, then the list is out of order.
Otherwise, we check if the rest of
`s`

is in order.

You should verify for yourself that a Python implementation of this for linked lists is similar.

Use Ok to unlock and test your code:

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

## Sets as Ordered Lists

A set is a type of collection that stores unique elements. The main operation associated with sets is checking whether a given value is in a set.

There is no such built-in set data type in Scheme, but one way to represent a set is by using an ordered list, where the ordering is used to make union/intersection functions more convenient. The following few questions explore this idea. Specifically, we will represent sets using Scheme lists ordered from least to greatest with no repeated elements.

### Q5: Add

First, 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.

We've provided a function `empty?`

which returns `True`

if the given set `s`

has
no elements.

```
(define (empty? s) (null? s))
(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
```

Inserting `v`

into a sorted list is analogous to finding `v`

in a sorted list.
When we know that everything in `s`

is larger than `v`

, then we know that's the
appropriate location to include `v`

.

Video walkthrough: https://youtu.be/H49bWAcT_pk

### Q6: Contains

Next, define `contains?`

, which returns whether a set `s`

contains value `v`

.

```
; Sets as sorted lists
(define (contains? s v)
(cond ((empty? s) #f)
((> (car s) v) #f)
((= (car s) v) #t)
((< (car s) v) (contains? (cdr s) v))) )
```

Use Ok to unlock and test your code:

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

Main ideas:

- If the beginning of
`s`

is equal to`v`

, then we're done. - If the beginning of
`s`

is smaller than`v`

, then`v`

could appear in the rest of`s`

. - If the beginning of
`s`

is larger than`v`

, then**all**the items of`s`

are larger than`v`

. So,`v`

cannot be in`s`

.

Video walkthrough: https://youtu.be/p3N-FhLjspg

### Q7: Intersect and Union

Finally, define `intersect`

, which returns a set containing only values that
appear in *both* sets `s`

and `t`

, and `union`

, which returns a set containing
all values that appear in *either* set `s`

or `t`

.

Your implementation for both functions should run in linear time in the length of the input sets.

```
(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)))) )
(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
```

`union`

and `intersect`

are quite similar. The main difference is that we
include items in `union`

that get skipped in `intersect`

(i.e. when `(car s)`

and `(car t)`

differ).

Video walkthrough: https://youtu.be/EWxT_Id9UlM