DrRacket Scheme代写: CSE 1729 Problem Set 4

Note: Whenever we use the terms iterative process or iterative form, we are talking about tail- recursive code. When we use the terms recursive process or recursive form we are talking about code that is not tail-recursive. Both iterative and recursive processes are found in recursive functions.

1. Abstracting the summation of a series
(a) In problem set 3 you wrote a function (new-cos x n) that calculated the sum

Xn k=0

( 1)k

x2k (2k)!

.

Define (new-cos x n) using the generalized sum function g-sum from this week’s lab. Note: the lab solution will have this, available Wednesday.
Of course, your new and improved definition of new-cos should not be recursive itself and should rely on g-sum to do the hard work.

2. (b)  The definition of g-sum from lab (the one I did in any case) is a recursive process. Write an iterative version g-sum-i that solves the same problems as g-sum in an iterative fashion. Demonstrate that it works by using it to define new-cos-i, an iterative version of new-cos. (Note: if your version of g-sum is iterative, write a recursive version that you can use to define new-cos and rename the one using the iterative g-sum to new-cos-i.) The names need to match these for testing.
3. (c)  Show that your cosine functions work for n values of 1, 50, and 100 for a couple of different x values. Remember that x is in radians.

2. Abstracting the product of a series
(a) The function g-sum is an abstraction of the sigma notation for summation:

Xb
f (n) = f (a) + · · · + f (b)

n=a
Write a function (g-product term a b) that abstracts the pi notation for the product of

a series:

Yb
f (n) = f (a) ⇥ · · · ⇥ f (b)

n=a

2. (b)  If your g-product function is in a recursive form, write a second one that is in the iterative form, and vice-versa (that is, you should write 2 versions of g-product, one recursive and one iterative). Name the recursive one g-product , and the iterative one g-product-i
3. (c)  Use your product functions to define an function (pi-approx n) that returns an approxi- mation of ⇡ using the first n terms of the following:

   ⇡=2⇥4⇥4⇥6⇥6⇥8⇥··· 4335577

   1

You will need to define appropriate function(s) for term.
(d) Show that your pi-approx function works for 1, 100, and 1000. What do these tests

demonstate to you?

3. Wecanabstractawayfromsumandproducttoamoregeneralfunction,(accumulatecombiner null-value term a next b). accumulate takes the same term and range specifications (term, a and b) as in sum and product, together with a next function that gives you the replacement for a on the recursive call, a combiner function of 2 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 initial value to combine each term to. To get the behavior of g-sum, set the next function to one that adds 1 to its argument, the combiner function to +, and the null-value to 0.

1. (a)  Write accumulate in either a recursive or iterative form.
2. (b)  Use accumulate to define g-sum-acc and g-product-acc, which perform the same func-

   tions as g-sum and g-product from the previous problems.

3. (c)  Demonstrate that these can be used to define new-sin-acc and pi-approx-acc, versions

   of new-cos and pi-approx (use the same test values).

4. Recall the definition of the derivative of a function from calculus (you will not need to know

any calculus to solve this problem):

f0(x) = lim f(x + h) f(x) h!0 h

By choosing very small values for h in the above equation, we can get a good approximation of f0(x).

1. (a)  Write a function (call it der for derivative) in Scheme that takes a function f and a value for h as formal parameters and returns the function g defined by the rule

   g(x)= f(x+h) f(x). h

   (As mentioned above, for small h, g is a good approximation for the derivative of f. Important note: Your function should take a function and a number h as arguments, and return a function.)

2. (b)  Compare dcos, the derivative of cos(x), as computed by your function with h = .01, with the function sin(x) over at least 4 values (0, ⇡/2, ⇡, 3⇡/4).
3. (c)  Write a function (fun x)that computes 3×2 2x + 7. As with the previous, compare your calculated derivative with 6x 2 for a few values of x.

5. In the lab you worked with function composition; here we do that and extend it to other ways of combining functions.

(a) Using your comp function from the lab (or the one in the solution), write a function (complement f) that takes a boolean function (one that evaluates to true or false) of one parameter, and returns a boolean function that evaluates to the complement, that is, the new function evaluates to true for all values where the original evaluates to false, and vice-versa.

2

(b) Define a function to add two functions. We define function addition as follows: for two functions of one variable f and g, the sum of the functions, f + g, is the function defined as

(f + g)(x) = f(x) + g(x)
Similarly we define function multiplication: for two functions of one variable f and g, the

product of the functions, f · g, is the function defined as (f · g)(x) = f(x)g(x)

Define two Scheme functions, (fun-sum f g) and (fun-product f g) that take two func- tions of one variable, and produce the functions corresponding to the addition and multipli- cation of their two arguments respectively. Remember, as was the case with composition, that these functions return functions. As an example:

>(define ssr (fun-product sqrt square)) >(ssr 4)
32
>((fun-sum sin cos) 0.0)

1

6. This is an optional question; I suggest you try it, but it will not count toward the problem set grade.

(a) Ok so now we use a little bit of calculus. The product rule for derivatives says if h(x) = f(x)g(x) and both f and g are differentiable, then h0(x) = f0(x)g(x) + f(x)g0(x). So let’s see if our functions can give us something similar.
Write a function (der-product-rule f g) that returns the derivative of the product of f and g using the product rule. Use your der function (with a fairly small h value, .0001 say) to get approximations of f0(x) and g0(x); usefun-sumandfun-productwhere appropriate.

2. (b)  An alternative way to find the derivative of the product of two functions is to use your der function on the product of the two functions obtained using fun-product. Write a Scheme function (der-product-direct f g) that uses that approach and returns the derivative (a function).
3. (c)  Now that you have these, do this test: define a couple of functions f and g, use your (der-product-rule f g) and (der-product-direct f g) to get estimates of the deriva- tive of their product. Evaluate these derivatives for a number of values of x and report how well they match. You might want to play around with various functions to find something interesting, and something that you can solve on paper so you know what to expect.

Once you have finished:
1. Save your work to a file using an appropriate filename (using the following convention: last-

name-firstname-CSE1729-Problem-Set4.rkt) and preserving the .rkt file extension. 2. Submit your solution file for grading via the HuskyCT site.

3