[edit]

Homework 3

Template

Type the following command at the terminal to copy the template file to the current directory (note the period at the end):

cp ~cs61as/autograder/templates/hw3.rkt .

Or you can download the template here.

Autograder

If you are working on the lab computers, the grader command will run the autograder. If you are working on your own personal machine, you should download grader.rkt and the HW 3 tests.

Exercise 1: Invariant for Fast Exponentiation

Here is the fast-expt procedure from earlier in this lesson:

(define (even? n)
  (= (remainder n 2) 0))

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

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

(Hint: Using the observation that (b^n/2)² = (b²)^n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a bⁿ is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

Exercise 2: Golden Ratio (Optional)

Read the subsection on finding fixed points of functions in SICP, and do Exercise 1.35.

Exercise 3: `cont-frac`

Part 1

An infinite continued fraction is an expression of the form:

[mathjax]f=\frac{N_1}{D_1+\frac{N_2}{D_2+\frac{N_3}{D_3+\cdots}}}[/mathjax]

As an example, one can show that

[mathjax]\frac{1}{\phi}=\frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots}}}[/mathjax]

where [mathjaxinline]\phi=\frac{1+\sqrt{5}}{2}[/mathjaxinline] is the golden ratio. One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation—a so-called [mathjaxinline]k[/mathjaxinline]-term finite continued fraction—has the form:

[mathjax]\frac{N_1}{D_1+\frac{N_2}{\ddots+\frac{N_k}{D_k}}}[/mathjax]

Suppose that n and d are procedures of one argument (the term index [mathjaxinline]i[/mathjaxinline]) that return the [mathjaxinline]N[/mathjaxinline] and [mathjaxinline]D[/mathjaxinline] of the [mathjaxinline]i[/mathjaxinline]-th term of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the [mathjaxinline]k[/mathjaxinline]-term finite continued fraction. Check your procedure by approximating [mathjaxinline]\frac{1}{\phi}[/mathjaxinline] using

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?

Part 2

If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Part 3

In 1737, Swiss mathematician Leonhard Euler showed that

[mathjax] e - 2=\frac{N_1}{D_1+\frac{N_2}{D_2+\frac{N_3}{D_3+\cdots}}} [/mathjax]

for the parameters

[mathjax] \begin{cases} N_i = 1\\ D_i = 1,2,1,1,4,1,1,6,1,1,8,\cdots \end{cases} [/mathjax]

where [mathjaxinline]e[/mathjaxinline] is the base of natural logarithms. Write a program that uses your cont-frac procedure to approximate [mathjaxinline]e[/mathjaxinline] using Euler's expansion.

Exercise 4: `next-perf`

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 consecutive integers starting with n until a perfect number is found. Then you can evaluate (next-perf 29) to solve the problem. Note that your procedure should be able to handle any non-negative integer input.

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 5: Interchanging Base Cases

Here is the definition of count-change program from earlier in this lesson:


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

(define (cc amount kinds-of-coins)
  (cond [(= amount 0) 1]
        [(or (< amount 0) (empty? kinds-of-coins)) 0]
        [else (+ (cc amount
                     (bf kinds-of-coins))
                 (cc (- amount
                        (first kinds-of-coins))
                     kinds-of-coins))] ))

Explain the effect of interchanging the order in which the base cases in the cc procedure 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)
  (cond
    [(or (< amount 0) (empty? kinds-of-coins)) 0]
    [(= amount 0) 1]
    [else ... ] ) ) ; as in the original version

Exercise 6: Invariant for Exponentiation

Here is the iterative exponentiation procedure from earlier in this lesson:

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product))))

Give an algebraic formula relating the values of the parameters b, n, counter, and product of the iterative exponentiation procedure defined above.

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