These exercises are due at the beginning of class on Thursday, March 6. In each case, you should submit the source code for your procedure and also show what happens when your procedure is invoked, in enough different cases to satisfy me that it works as described. As in exercise set #1, use submit to create a log file and elm to mail it to me.

1. Deep recursion.

Design, write, and test a Scheme procedure contents that takes a (possibly null) tree of real numbers as argument and returns a list containing all the numbers in the tree, in ascending numerical order.

(contents '(((6 8 4) (7 2)) 3 (1 (9 0)) ((12 5) 10)))
===> (0 1 2 3 4 5 6 7 8 9 10 12)
(contents '()) ===> ()
(contents '(3 -8)) ===> (-8 3)
(contents '(((((4)))) 2.5)) ===> (2.5 4)

(Hint: Review Program 4.3 on page 98 of the text.)

2. Local bindings.

The nth harmonic number of order k, for any positive integers n and k, is the sum of the reciprocals of the kth powers of the positive integers from 1 to n. For example, the seventh harmonic number of order three is 1/1³ + 1/2³ + 1/3³ + 1/4³ + 1/5³ + 1/6³ + 1/7³, which is 1/1 + 1/8 + 1/27 + 1/64 + 1/125 + 1/216 + 1/343, or 9822481/8232000.

Design, write, and test a Scheme procedure that takes n, the number of terms, and k, the order (that is, the exponent), as arguments, and returns the nth harmonic number of order k.

3. Prime numbers.

A natural number is prime if it is greater than or equal to 2 and none of the integers greater than 1 and less than itself evenly divides it. For example, the number 11 is prime, because none of the integers from 2 to 10 divides it; but 221 is not prime, since it is evenly divisible by 13 and by 17.

Design, write, and test a Scheme predicate prime? that takes a natural number as its argument and determines whether it is prime. For extra credit, write a version that performs as few divisions as possible in the course of computing its answer.

This document is available on the World Wide Web as

http://www.math.grin.edu/courses/Scheme/spring-1997/exercise-2.html