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

**Submission.** See the online submission instructions. We have
provided a starter file for the questions below.

**Readings.** Sections 2.1-2.3 of the
online lecture notes.

**Q1.** Recall the `rlist` abstract data type defined in the lecture notes:

empty_rlist = None def rlist(first, rest): """Construct a recursive list from its first element and the rest.""" return (first, rest) def first(s): """Return the first element of a recursive list s.""" return s[0] def rest(s): """Return the rest of the elements of a recursive list s.""" return s[1]

Write iterative and recursive functions that reverse a given recursive list,
producing a new recursive list with the elements in reverse order. Use only the
`rlist` constructor and `first` and `rest` selectors to manipulate
recursive lists. (You may use helper functions, but do not duplicate the
functionality of `len_rlist` or `getitem_rlist`.)

def reverse_rlist_iterative(s): """Return a reversed version of a recursive list s. >>> primes = rlist(2, rlist(3, rlist(5, rlist(7, empty_rlist)))) >>> reverse_rlist_iterative(primes) (7, (5, (3, (2, None)))) """ "*** YOUR CODE HERE ***" def reverse_rlist_recursive(s): """Return a reversed version of a recursive list s. >>> primes = rlist(2, rlist(3, rlist(5, rlist(7, empty_rlist)))) >>> reverse_rlist_recursive(primes) (7, (5, (3, (2, None)))) """ "*** YOUR CODE HERE ***"

**Q2.** Write recursive and iterative functions that take two recursive lists
and produce a new recursive list with their elements interleaved. In other
words, the resulting list should have the first element of the first list, the
first of the second, the second element of the first list, the second of the
second, and so on. If the two lists are not the same size, then the leftover
elements of the longer list should still appear at the end. The same
restrictions as in Q1 apply here.

*Hint*: Feel free to make use of either reverse function in
`interleave_iterative`.

def interleave_recursive(s0, s1): """Interleave recursive lists s0 and s1 to produce a new recursive list. >>> evens = rlist(2, rlist(4, rlist(6, rlist(8, empty_rlist)))) >>> odds = rlist(1, rlist(3, empty_rlist)) >>> interleave_recursive(odds, evens) (1, (2, (3, (4, (6, (8, None)))))) >>> interleave_recursive(evens, odds) (2, (1, (4, (3, (6, (8, None)))))) >>> interleave_recursive(odds, odds) (1, (1, (3, (3, None)))) """ "*** YOUR CODE HERE ***" def interleave_iterative(s0, s1): """Interleave recursive lists s0 and s1 to produce a new recursive list. >>> evens = rlist(2, rlist(4, rlist(6, rlist(8, empty_rlist)))) >>> odds = rlist(1, rlist(3, empty_rlist)) >>> interleave_iterative(odds, evens) (1, (2, (3, (4, (6, (8, None)))))) >>> interleave_iterative(evens, odds) (2, (1, (4, (3, (6, (8, None)))))) >>> interleave_iterative(odds, odds) (1, (1, (3, (3, None)))) """ "*** YOUR CODE HERE ***"

**Interval Arithmetic**

**Acknowledgments.** This interval arithmetic example is based on 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, subtracting, 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. >>> str_interval(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(interval(-1, 2), interval(4, 8))) '3 to 10' """ lower = lower_bound(x) + lower_bound(y) upper = upper_bound(x) + upper_bound(y) return 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(interval(-1, 2), 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 interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))

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

def interval(a, b): """Construct an interval from a to b.""" "*** YOUR CODE HERE ***" 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 ***"

**Q4.** 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. >>> str_interval(div_interval(interval(-1, 2), interval(4, 8))) '-0.25 to 0.5' """ "*** YOUR CODE HERE ***" reciprocal_y = interval(1/upper_bound(y), 1/lower_bound(y)) return mul_interval(x, reciprocal_y)

**Q5.** Using reasoning analogous to Alyssa's, define a subtraction function for
intervals:

def sub_interval(x, y): """Return the interval that contains the difference between any value in x and any value in y. >>> str_interval(sub_interval(interval(-1, 2), interval(4, 8))) '-9 to -2' """ "*** YOUR CODE HERE ***"

**Q6.** 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 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.

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:

def make_center_percent(c, p): """Construct an interval from center and percentage tolerance. >>> str_interval(make_center_percent(2, 50)) '1.0 to 3.0' """ "*** YOUR CODE HERE ***" def percent(x): """Return the percentage tolerance of interval x. >>> percent(interval(1, 3)) 50.0 """ "*** YOUR CODE HERE ***"

**Q7.** 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`

*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".

def quadratic(x, a, b, c): """Return the interval that is the range the quadratic defined by a, b, and c, for domain interval x. This is the less accurate version which treats each instance of t as a different value from the interval. See the extra for experts question for exploring why this is not _really_ correct and to write a more precise version. >>> str_interval(quadratic(interval(0, 2), -2, 3, -1)) '-9 to 5' >>> str_interval(quadratic(interval(1, 3), 2, -3, 1)) '-6 to 16' """ "*** YOUR CODE HERE ***"

**Q8.** (Extra for Experts) 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 `a` and `b`, and show
that `par1` and `par2` can give different results. You will get the most
insight by using intervals whose width is a small percentage of the center
value:

# These two intervals give different results for parallel resistors: "*** YOUR CODE HERE ***"

**Q9.** (Extra for Experts) 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 Reference 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 an explanation
string:

def multiple_reference_explanation(): return """The multiple reference problem..."""

**Q10.** (Extra for Experts) Write a new version of `quadratic`,
`accurate_quadratic`, that takes the multiple reference problem into account
and produces a tighter interval than our original solution. Make sure that your
implementation returns the smallest such interval.

*Hint*: the derivative is `f'(t) = 2 * a * t + b`, and so the extreme point of
the quadratic is `-b/(2*a)`:

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