MCS-177 Homework 4, Fall 1999

Due: October 13, 1999

1. The range from a to b can only be divided into two smaller ranges if it has at least two integers in it. Thus, you can't use the general approach of dividing the range in half if the range has fewer than two integers in it. You will need to do something else instead.

2. The approximate midpoint of the range from a to b can be calculated as (quotient (+ a b) 2). Suppose we call this approximate midpoint m. One possibility would be to take the two subranges as running from a to m-1 and from m to b. Another possibility would be to take the two subranges as running from a to m and from m+1 to b. One of these options is better than the other, because it gives two equal size subranges when that is possible (that is, when the original range had an even number of integers in it).

3. Although this is a homework problem and not a lab, it would be a shame to have me tell you that your procedure doesn't work when DrScheme could tell you the same thing earlier, without a grade attached.

4. Your answer to part (b) of the problem should be of the form: "The number of additions done is Theta(something), where n is the number of integers in the range." Of course, if possible you should use a real Greek uppercase Theta character rather than the word "Theta," and you should replace "something" by the appropriate expression involving n. For example, if the number of additions grows quadratically with n (which I hope it doesn't), you would write "The number of additions is Theta(n²), where n is the number of integers in the range." Whatever assertion of this form you make, you should then justify.

Instructor: Max Hailperin