CSE 1729 – Introduction to Principles of Programming Due September 18, 2016 Problem Set 2
For this assignment, you will hand in 1 document, a Racket file. You will use the same labeling convention as in Problem Set 1.
Remember: code questions should always include at least two test cases.
1. Recall from class the definition of number-sum, which computes the sum of the first n numbers:
(define (number-sum n) (if (= n 0)
0
(+ n (number-sum (- n 1)))))
(a) Adapt the function to one named (even-sum n) that computes the sum of the first n even numbers (remember that the first even number is 0). (So (even-sum 4) should return 12, the sum of the first 4 even numbers: 0+2+4+6.)
(b) Evaluate your function at 1, 2, 3, 4, 5, 6, and 7. What does this sequence of numbers look like, and does that make sense?
(c) Adapt the function into (sum-from-to a b) that it computes the sum of the all integers from a to b, so (sum-from-to 3 5) should evaluate to 12. If a is greater that b, it should evaluate to 0.
2. Write a recursive function (diff-prod k) that, given a positive integer k > 1, computes the
product
k 1
(Experiment with the results for some various values of k; this might suggest a simple non-
✓1 1◆✓1 1◆···✓1 1◆ . 23k
| {z }
recursive way to formulate this function.) 3.
If0z<1,X1zi= 1 i=0 1 z
(a) Write a Scheme function (finite-sum-of-powers z k) that evaluates to the sum of the first k + 1 terms in the above sum (that is, the sum from 0 to k). You can use Scheme’s expt function, as (expt z n) evaluates to zn.
(b) We will now measure how large k needs to be in the above function to provide a good
approximation of the infinite sum. You will write a Scheme function (terms-needed z
tol) that will evaluate to the number of terms in the infinite sum needed to be within tol,
that is, the smallest k such that the difference between 1 and (finite-sum-of-powers 1 z
z k) is less than tol. You can assume for this function that 0 z < 1. 1
4. (a)
Write a function (fin-alt-series k) that, given a positive integer k, returns the sum of the first k terms of the infinite series:
4 4+4 4+4 ···. 13579
Observe that signs alternate in this series; one easy way to implement an alternating sign is to use the function ( 1)`, which is 1 when ` is even, and 1 when ` is odd. As with the problem above, you could use the built-in Scheme function (expt x k), which returns xk (and so provides a straightforward way to compute ( 1)`).
Depending on how you wrote your code, Scheme may have produced exact output of the form ab. To coerce Scheme to give you an approximation in decimal form, change the
At first glance, the problem of defining (terms-needed z tol) appears a little challenging, because it’s not at all obvious how to express it in terms of a smaller problem. But you might consider writing a helper function (first-value-k-or-higher z tol k) that evaluates to k if (finite-sum-of-powers z k) is within tol of the right answer, otherwise calls itself recursively with larger k.
(c) If you have tested your function in the previous problem, you may have observed that the number of terms needed for a given tol value varies with the size of z. Informally, how do these values vary? When does the approximation work best, and when does it work the worst from the perspective of the number of terms needed?
c
constant 4 in your code to 4.0.
(b) Use your function to sum the first 100 terms of this series.
(c) Now compute the sum of the first 100,000 terms. Does this number look (roughly) familiar?
(d) Consider the definition of your last function. To compute the 100,000 terms, how many
calls to expt were made? What are the actual values passed to each call?
(e) Revise the function you just wrote to eliminate the repeated invocations of expt. (Your function should not use expt at all but somehow compute the signs on its own.) You can introduce a helper function with more arguments if you wish! Your revised function should be named fin-alt-series-2
5. Consider the following series: X1 1 x= i!
this series, that is
(finite-mystery-series k) = Xk 1 i=0 i!
Note: for this to work, 0! must be equal to 1.
(a) Write the Scheme function (finite-mystery-series k) as defined above. It should work
for any non-negative integer k. You will also need to write a factorial function. 2
i=0
As with the previous problem, you are to write a Scheme routine to calculate the finite sums of
(b) Run your function on a number of different k values. What do you observe? What does this finite series seem to approximate?
(c) How does this finite series approximation compare with the one from Problem 4? Once you have finished:
1. Save your work to a file using an appropriate filename (using the following convention: last- name-firstname-CSE1729-Problem-Setk.rkt) and preserving the .rkt file extension.
2. Submit your solution file for grading via the HuskyCT site.
3