MCS-177 Homework 4, Spring 2001
Due: March 14, 2001
Do exercise 4.18 on page 104. Here are some hints that may help you
with this problem:
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
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).
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.
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(n2), where n is the number of
integers in the range." Whatever assertion of this form you make, you
should then justify.
Instructor: Max Hailperin