# Homework 5

*Due by 11:59pm on Wednesday, 9/27*

## Instructions

Download hw05.zip.

**Submission:** When you are done, submit with
`python3 ok --submit`

.
You may submit more than once before the deadline; only the final submission
will be scored. Check that you have successfully submitted your code on
okpy.org.
See Lab 0
for more instructions on submitting assignments.

**Using Ok:** If you have any questions about using Ok, please
refer to this guide.

**Readings:** You might find the following references
useful:

# Required Questions

### Q1: Replace Leaf

Define `replace_leaf`

, which takes a tree `t`

, a value `old`

, and a value `new`

.
`replace_leaf`

returns a new tree that's the same as `t`

except that every leaf
value equal to `old`

has been replaced with `new`

.

```
def replace_leaf(t, old, new):
"""Returns a new tree where every leaf value equal to old has
been replaced with new.
>>> yggdrasil = tree('odin',
... [tree('balder',
... [tree('thor'),
... tree('loki')]),
... tree('frigg',
... [tree('thor')]),
... tree('thor',
... [tree('sif'),
... tree('thor')]),
... tree('thor')])
>>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
>>> print_tree(replace_leaf(yggdrasil, 'thor', 'freya'))
odin
balder
freya
loki
frigg
freya
thor
sif
freya
freya
>>> laerad == yggdrasil # Make sure original tree is unmodified
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q replace_leaf`

### Q2: Towers of Hanoi

A classic puzzle called the Towers of Hanoi is a game that consists of three
rods, and a number of disks of different sizes which can slide onto any rod.
The puzzle starts with `n`

disks in a neat stack in ascending order of size on
a `start`

rod, the smallest at the top, forming a conical shape.

The objective of the puzzle is to move the entire stack to an `end`

rod,
obeying the following rules:

- Only one disk may be moved at a time.
- Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.

Complete the definition of `move_stack`

, which prints out the steps required to
move `n`

disks from the `start`

rod to the `end`

rod without violating the
rules.

```
def print_move(origin, destination):
"""Print instructions to move a disk."""
print("Move the top disk from rod", origin, "to rod", destination)
def move_stack(n, start, end):
"""Print the moves required to move n disks on the start pole to the end
pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q move_stack`

## Interval

**Acknowledgements.** This interval arithmetic example is based on
a classic problem from Structure and Interpretation of Computer Programs,
Section 2.1.4.

**Introduction.** Alyssa P. Hacker is designing a system to help people
solve engineering problems. One feature she wants to provide in her
system is the ability to manipulate inexact quantities (such as
measured parameters of physical devices) with known precision, so that
when computations are done with such approximate quantities the results
will be numbers of known precision.

Alyssa's idea is to implement interval arithmetic as a set of arithmetic operations for combining "intervals" (objects that represent the range of possible values of an inexact quantity). The result of adding, subracting, multiplying, or dividing two intervals is itself an interval, representing the range of the result.

Alyssa postulates the existence of an abstract object called an "interval" that has two endpoints: a lower bound and an upper bound. She also presumes that, given the endpoints of an interval, she can construct the interval using the data constructor interval. Using the constructor and selectors, she defines the following operations:

```
def str_interval(x):
"""Return a string representation of interval x."""
return '{0} to {1}'.format(lower_bound(x), upper_bound(x))
def add_interval(x, y):
"""Return an interval that contains the sum of any value in interval x and
any value in interval y."""
lower = lower_bound(x) + lower_bound(y)
upper = upper_bound(x) + upper_bound(y)
return interval(lower, upper)
```

### Q3: Interval Abstraction

Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. She has implemented the constructor for you; fill in the implementation of the selectors.

```
def interval(a, b):
"""Construct an interval from a to b."""
return [a, b]
def lower_bound(x):
"""Return the lower bound of interval x."""
"*** YOUR CODE HERE ***"
def upper_bound(x):
"""Return the upper bound of interval x."""
"*** YOUR CODE HERE ***"
```

Use Ok to unlock and test your code:

```
python3 ok -q interval -u
python3 ok -q interval
```

Louis Reasoner has also provided an implementation of interval multiplication. Beware: there are some data abstraction violations, so help him fix his code before someone sets it on fire.

```
def mul_interval(x, y):
"""Return the interval that contains the product of any value in x and any
value in y."""
p1 = x[0] * y[0]
p2 = x[0] * y[1]
p3 = x[1] * y[0]
p4 = x[1] * y[1]
return [min(p1, p2, p3, p4), max(p1, p2, p3, p4)]
```

Use Ok to unlock and test your code:

```
python3 ok -q mul_interval -u
python3 ok -q mul_interval
```

### Q4: Sub Interval

Using reasoning analogous to Alyssa's, define a subtraction function for intervals. Try to reuse functions that have already been implemented.

```
def sub_interval(x, y):
"""Return the interval that contains the difference between any value in x
and any value in y."""
"*** YOUR CODE HERE ***"
```

Use Ok to unlock and test your code:

```
python3 ok -q sub_interval -u
python3 ok -q sub_interval
```

### Q5: Div Interval

Alyssa implements division below by multiplying by the reciprocal of
`y`

. Ben Bitdiddle, an expert systems programmer, looks over Alyssa's
shoulder and comments that it is not clear what it means to divide by
an interval that spans zero. Add an `assert`

statement to Alyssa's code
to ensure that no such interval is used as a divisor:

```
def div_interval(x, y):
"""Return the interval that contains the quotient of any value in x divided by
any value in y. Division is implemented as the multiplication of x by the
reciprocal of y."""
"*** YOUR CODE HERE ***"
reciprocal_y = interval(1/upper_bound(y), 1/lower_bound(y))
return mul_interval(x, reciprocal_y)
```

Use Ok to unlock and test your code:

```
python3 ok -q div_interval -u
python3 ok -q div_interval
```

### Q6: Par Diff

After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways:

`par1(r1, r2) = (r1 * r2) / (r1 + r2)`

or

`par2(r1, r2) = 1 / (1/r1 + 1/r2)`

He has written the following two programs, each of which computes the
`parallel_resistors`

formula differently::

```
def par1(r1, r2):
return div_interval(mul_interval(r1, r2), add_interval(r1, r2))
def par2(r1, r2):
one = interval(1, 1)
rep_r1 = div_interval(one, r1)
rep_r2 = div_interval(one, r2)
return div_interval(one, add_interval(rep_r1, rep_r2))
```

Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint.

Demonstrate that Lem is right. Investigate the behavior of the system
on a variety of arithmetic expressions. Make some intervals `r1`

and
`r2`

, and show that `par1`

and `par2`

can give different results.

```
def check_par():
"""Return two intervals that give different results for parallel resistors.
>>> r1, r2 = check_par()
>>> x = par1(r1, r2)
>>> y = par2(r1, r2)
>>> lower_bound(x) != lower_bound(y) or upper_bound(x) != upper_bound(y)
True
"""
r1 = interval(1, 1) # Replace this line!
r2 = interval(1, 1) # Replace this line!
return r1, r2
```

Use Ok to test your code:

`python3 ok -q check_par`

### Q7: Multiple References

Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that the problem is multiple references to the same interval.

The Multiple References Problem: a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated.

Thus, she says, `par2`

is a better program for parallel resistances
than `par1`

. Is she right? Why? Write a function that returns a string
containing a written explanation of your answer:

```
def multiple_references_explanation():
return """The multiple reference problem..."""
```

### Q8: Quadratic

Write a function `quadratic`

that returns the interval of all values
`f(t)`

such that `t`

is in the argument interval `x`

and `f(t)`

is a
quadratic function:

`f(t) = a*t*t + b*t + c`

Make sure that your implementation returns the smallest such interval, one that does not suffer from the multiple references problem.

*Hint*: the derivative `f'(t) = 2*a*t + b`

, and so the extreme
point of the quadratic is `-b/(2*a)`

:

```
def quadratic(x, a, b, c):
"""Return the interval that is the range of the quadratic defined by
coefficients a, b, and c, for domain interval x.
>>> str_interval(quadratic(interval(0, 2), -2, 3, -1))
'-3 to 0.125'
>>> str_interval(quadratic(interval(1, 3), 2, -3, 1))
'0 to 10'
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q quadratic`

# Extra Questions

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

### Q9: Polynomial

Write a function `polynomial`

that takes an interval `x`

and a list of
coefficients `c`

, and returns the interval containing all values of `f(t)`

for
`t`

in interval `x`

, where:

`f(t) = c[k-1] * pow(t, k-1) + c[k-2] * pow(t, k-2) + ... + c[0] * 1`

Like `quadratic`

, your `polynomial`

function should return the smallest such
interval, one that does not suffer from the multiple references problem.

*Hint*: You can approximate this result. Try using Newton's
method.

```
def polynomial(x, c):
"""Return the interval that is the range of the polynomial defined by
coefficients c, for domain interval x.
>>> str_interval(polynomial(interval(0, 2), [-1, 3, -2]))
'-3 to 0.125'
>>> str_interval(polynomial(interval(1, 3), [1, -3, 2]))
'0 to 10'
>>> str_interval(polynomial(interval(0.5, 2.25), [10, 24, -6, -8, 3]))
'18.0 to 23.0'
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q polynomial`