*Due by 11:59 PM on (that is, the end of) Tuesday, 7/3*

**This homework must be submitted online.** We do not
require a paper copy. If you would like a reader to give you written feedback
on your homework, submit a paper copy to the homework box.

**To turn in the electronic copy**, submit all of your
answers in a file named `hw4.py`. Follow the instructions here to submit the electronic copy.

**Readings.** All problems in this homework can be solved
with the subset of Python 3 introduced in sections 1-2.2 of the lecture
notes.

If you would like, you can use the template file `hw4.py`

.
To copy this file to your lab account you can run the command:

cp ~cs61a/lib/hw/hw04/hw4.py .

to copy it into your current directory.

This interval arithmetic example is based on SICP, Section 2.1.4.

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 make_interval. Using the constructor and
selectors, she defines the following operations:

def str_interval(x): """Return a string representation of interval x. >>> str_interval(make_interval(-1, 2)) '-1 to 2' """ 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. >>> str_interval(add_interval(make_interval(-1, 2), make_interval(4, 8))) '3 to 10' """ lower = lower_bound(x) + lower_bound(y) upper = upper_bound(x) + upper_bound(y) return make_interval(lower, upper) def mul_interval(x, y): """Return the interval that contains the product of any value in x and any value in y. >>> str_interval(mul_interval(make_interval(-1, 2), make_interval(4, 8))) '-8 to 16' """ p1 = lower_bound(x) * lower_bound(y) p2 = lower_bound(x) * upper_bound(y) p3 = upper_bound(x) * lower_bound(y) p4 = upper_bound(x) * upper_bound(y) return make_interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))

**Q1.** Alyssa's program is incomplete because she has not
specified the implementation of the interval abstraction. Define the constructor
`make_interval` and selectors `lower_bound` and `upper_bound` in terms of two-element tuples.

**Q2.** Write `sum_intervals`, which takes a sequence (tuple) of intervals
and returns the interval representing their sum. Add a doctest.

**Q3.** Alyssa implements division of two intervals
`x` and `y`
by multiplying `x` 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. >>> str_interval(div_interval(make_interval(-1, 2), make_interval(4, 8))) '-0.25 to 0.5' """ "*** YOUR CODE HERE ***" reciprocal_y = make_interval(1/upper_bound(y), 1/lower_bound(y)) return mul_interval(x, reciprocal_y)

*Hint:* It might help to write a local function `spans_zero` which returns `True` if the interval includes zero.

**Q4.** Using reasoning analogous to Alyssa's, define a
subtraction function, `sub_interval` for
intervals. Add a doctest.

**Q5.** After debugging her program, Alyssa shows it to a
potential user, who complains that her program solves the wrong problem. He
wants a program that can deal with numbers represented as a center value and an
additive tolerance; for example, he wants to work with intervals such as 3.5 +/-
0.15 rather than 3.35 to 3.65. Alyssa returns to her desk and fixes this problem
by supplying an alternate constructor and alternate selectors in terms of the
existing ones:

def make_center_width(c, w): """Construct an interval from center and width.""" return make_interval(c - w, c + w) def center(x): """Return the center of interval x.""" return (upper_bound(x) + lower_bound(x)) / 2 def width(x): """Return the width of interval x.""" return (upper_bound(x) - lower_bound(x)) / 2

Unfortunately, most of Alyssa's users are engineers. Real engineering situations usually involve measurements with only a small uncertainty, measured as the ratio of the width of the interval to the midpoint of the interval. Engineers usually specify percentage tolerances on the parameters of devices. For example an engineer might say a value is 5 with a percentage tolerance of 10% which would mean that the values can range from 4.5 to 5.5, since 10% of 5 is .5 and so we have (5 - 10% of 5) through (5 + 10% of 5).

Define a constructor `make_center_percent` that takes a center and a percentage tolerance
and produces the desired interval. You must also define a selector `percent` that produces the percentage tolerance for
a given interval. The center selector is the same as the one shown above.
*Hint:* The percentage tolerance is defined in terms of the interval's
center and width. Make use of the two other selectors already provided.

**Q6.** 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) = a * t * t + b * t + c

where `a`, `b`, and `c` are also
parameters.

*Note:* You might have noticed that we're calculating a much
larger interval than what is the *true* range of possible outputs given
the input interval `x`, we explore this problem
in questions in the Extra for Experts section that deals with the "Multiple
Reference Problem".

**Q7.** Express the order of growth in time of the
following functions, using big-Theta notation.

def one(n): return n def two(n): if n > 10 or n < 0: return n return two(n+1) def three(n): if n <= 0: return 0 elif n % 2 == 0: return 2 + three(n/2) else: return 1 + three(n-1) def four(n): if n == 0: return 0 else: return two(n) + four(n-1) def five(n): if n == 0: return 0 else: return three(n) + five(n-1) def six(n): total = 0 while n >= 0: total = total + four(n) n = n-1 return total

**Extra for Experts**

*Note*: "Extra for Experts" problems are completely
optional. You are encouraged to try these questions. However, these are
questions which either we consider more difficult than what we would consider asking
you on an exam or focus on ideas we are not concerned with in this course, so
please don't be discouraged if you don't solve them.

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

(r1 * r2) / (r1 + r2) and 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 = make_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 A and B, and use them in computing the expressions A/A and A/B. You will get the most insight by using intervals whose width is a small percentage of the center value.

**Q9.** 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? Include an explanation as a string in the
`hw4.py` file you submit.

**Q10.** Write a new version of `quadratic`, `accurate_quadratic`,
which takes the multiple references problem into account and returns a tighter
interval than our original solution.

*Hint*: The derivative is

f'(t) = 2 * a * t + b

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

**Q11.** Write a function `polynomial` that takes an interval `x` and a tuple of coefficients `c`,
and returns the (possibly approximate) 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 `accurate_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. Consider using Newton's
method. Feel free to use the code from `newton.py`

for this
question.