Lab 3:

Measuring Efficiency

This week is about the details. How fast is your program? How much memory does it need? While we won't emphasize this measurement of how good a program is in this course, it will be used in nearly all of your other CS classes.


finish this during section

Many of these exercises concern the change counting program on pages 40-41 of SICP.

Exercise 1.

Identify two ways to change the program to reverse the order in which coins are tried, that is, to change the program so that pennies are tried first, then nickels, then dimes, and so on.

Exercise 2.

Abelson and Sussman claim that this change would not affect the correctness of the computation. However, it does affect the efficiency of the computation.

Implement one of the ways you devised in exercise 1 for reversing the order in which coins are tried, and determine the extent to which the number of calls to cc is affected by the revision. Verify your answer on the computer, and provide an explanation.

Hint: limit yourself to nickels and pennies, and compare the trees resulting from (cc 5 2) for each order.

Exercise 3.

Modify the cc procedure so that its kinds-of-coins parameter, instead of being an integer, is a sentence that contains the values of the coins to be used in making change.

The coins should be tried in the sequence they appear in the sentence. For the count-change procedure to work the same in the revised program as in the original, it should call cc as follows:

(define (count-change amount)
  (cc amount ’(50 25 10 5 1)) )

Exercise 4.

Many Scheme procedures require a certain type of argument. For example, the arithmetic procedures only work if given numeric arguments. If given a non-number, an error results.

Suppose we want to write safe versions of procedures, that can check if the argument is okay, and either call the underlying procedure or return #f for a bad argument instead of giving an error. (We’ll restrict our attention to procedures that take a single argument.)

Write type-check. Its arguments are a function, a type-checking predicate that returns #t if and only if the datum is a legal argument to the function, and the datum.

Exercise 5.

We really don’t want to have to use type-check explicitly every time. Instead, we’d like to be able to use a safe-sqrt procedure:

> (safe-sqrt ’hello)
> (safe-sqrt 4)

Don’t write safe-sqrt! Instead, write a procedure make-safe that you can use this way:

> (define safe-sqrt (make-safe sqrt number?))

It should take two arguments, a function and a type-checking predicate, and return a new function that returns #f if its argument doesn’t satisfy the predicate.


do this in section if possible; finish the rest at home

Exercise 6.

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt.

For more information and a hint, see SICP Ex. 1.16

Exercise 7.

SICP Ex. 1.35: Show that the golden ratio is a fixed point of the transformation x -> 1 + 1/x, and use this fact to compute it by means of the fixed-point procedure.

Exercise 8.

SICP Ex. 1.37 and 1.38

Exercise 9.

A “perfect number” is defined as a number equal to the sum of all its factors less than itself. For example, the first perfect number is 6, because its factors are 1, 2, 3, and 6, and 1+2+3=6. The second perfect number is 28, because 1+2+4+7+14=28. What is the third perfect number?

Write a procedure (next-perf n) that tests numbers starting with n and continuing with n+1, n+2, etc. until a perfect number is found. Then you can evaluate (next-perf 29) to solve the problem.

Hint: you’ll need a sum-of-factors subprocedure.

[Note: If you run this program when the system is heavily loaded, it may take half an hour to compute the answer! Try tracing helper procedures to make sure your program is on track, or start by computing (next-perf 1) and see if you get 6.]

Exercise 10.

Explain the effect of interchanging the order in which the base cases in the cc procedure on page 41 of SICP are checked.

That is, describe completely the set of arguments for which the original cc procedure would return a different value or behave differently from a cc procedure coded as given below, and explain how the returned values would differ.

(define (cc amount kinds-of-coins)
    ((or (< amount 0) (= kinds-of-coins 0)) 0)
    ((= amount 0) 1)
    (else ... ) ) ) ; as in the original version

Exercise 11.

Give an algebraic formula relating the values of the parameters b, n, counter, and product of the expt and exp-iter procedures given near the top of page 45 of Abelson and Sussman.

(The kind of answer we’re looking for is “the sum of b, n, and counter times product is always equal to 37.”)

Exercise 12.

Do the following reading:

Project 1

Finish this before the deadline. Apart from that, we don't care when.

Do project 1