1.  In the previous problems set, you wrote generalized versions of the sum and product of terms in a sequence. Show that sum and product are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:

(accumulate  combiner null-value term  a next b)

accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out.

(a) Write accumulate using simple recursion and show how sum and product can both be defined as simple calls to accumulate.

(b)  In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. The nth Cata- lan number is given directly in terms of binomial coefficients (recall Lab 2) by

Cn =  ╱n(2n)、=  =  2(n)     for n ≥ 0

The first Catalan numbers for n = 0, 1, 2, 3, . . . are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, . . .

Define a SCHEME function, named (catalan n), which uses your accumulate function to compute the nth Catalan number using the definition above.

(c)  The Leibniz formula for π, named after Gottfried Leibniz, states that

π            1      1      1      1

4            3     5     7     9

Use your accumulate function to define a new SCHEME function, named (leibniz-pi using the definition above.

(d) Write another version of the accumulate function, named            (accumulate-tr  combiner null-value term  a next b)

which implements this same general accumulation function using tail recursion.

(e)  Use your tail-recursive version of accumulate, accumulate-tr, to define a SCHEME function, named (fact n) which computes the factorial function (n!).

(f)  Use your tail-recursive version of accumulate, accumulate-tr, to define a SCHEME function, named (e-to-x  x  n) which computes an approximation to ex  using the Maclaurin series as follows:

ex  = 0   = 1 + x +  +  +．．．

You should start with your implementation of the factorial function using accumulate-tr from Part e.

2.  (Pairing function.) A pairingfunction p is a function that places the natural numbers N = ←0, 1, 2, . . .} into one-to-one correspondence with the set of all pairs of natural numbers (usually denoted N×N).  It is somewhat surprising that such a function should exist at all: it shows that the set of natural  numbers has the same “size” as the set of all pairs of natural numbers. To be more precise, a pairing  function p takes two natural numbers x and y as arguments and returns a single number z with the  property that the original pair can always be determined exactly from the value z .  (In particular,

the function maps no more than one pair to any particular natural number.)

One pairing function is the following:

p(x , y) = 

if x  max(x , y)

if x = max(x , y)

(a) Write a SCHEME function (encode p) that computes the pairing function above.  (It should take a pair of integers as an argument and return a single integer.) The max function evalu- ates to the larger of its two arguments. An implementation is available as a SCHEME built-in function.

(b) As mentioned above, this function has the property that if (x , y)  (x′ , y ′ ) then p(x , y)  p(x′ , y ′ ):  it follows that, in principle, the pair (x , y) can be reconstructed from the single value z = p(x , y). In fact, the values x and y can be reconstructed from z = p(x , y) by

u(z) = , 一’z）2一’z）)

if z 一 (’z）2 < (’z）

if z 一 (’z）2 ≥ (’z）

Write a SCHEME function (decode  z) that takes as an argument an integer z and produces the pair (x , y) for which p(x , y) = z . You’ll need the floor function:  (floor x) returns the largest integer less than or equal to x (that is, it rounds x down to the nearest integer).

3.  In lecture, we proposed representing complex numbers, numbers of the form (a + bi), using pairs to store both the real part and the imaginary part. We presented convenience functions for creating complex numbers stored in SCHEME  pairs as well as some functions which operate on complex numbers (e.g. add-complex, mult-complex). In this question, we will expand on the functions we can apply to complex numbers.

(a)  The subtraction of two complex numbers, (a + bi) and (c + d i), in component form is given by:

(a, b) 一 (c, d) = (a 一 c, b 一 d)

Define a SCHEME function, named (sub-complex  c  d), which accepts two complex num-

bers represented by pairs and returns a complex number representing their difference.         (b)  The division of two complex numbers, (a + bi) and (c + d i), in component form is given by:

 = ╱   d(a)d2 、

Define a SCHEME function, named (div-complex  c  d), which accepts two complex num- bers represented by pairs and returns a complex number representing the first divided by the second.