MCS-177 Homework assignment 4 (Fall 2000)

Homework set 4 (due Thursday, October 19)

As always, if you complete a homework a day or more early, feel free to have us look it over before it's due. We'd be happy to give you feedback before you have to submit it.

Consider the following procedure for multiplying a by b:

(define multiply
  (lambda (a b) ;; b must be a non-negative integer
    (define loop
      (lambda (b acc) ;; returns ab + acc
        (if (= b 0)
            acc
            (loop (- b 1) (+ a acc)))))
    (loop b 0)))

Exactly how many additions does the procedure do? Express your answer as a function of a and/or b.

Exercise 4.14 on pages 101-102.
1. Compute 9²⁵ mod 11 by hand by the same method used by the procedure mod-expt on page 93.
2. Explain in your own words how this was faster than if you had used either the method on page 90 or on page 91. You should refer to the arithmetic you did in part (a) to illustrate your point.
Exercise 5.2 on page 112.
Be sure to test together-copies-of on two procedures such as + and stack.
Exercise 5.8 on page 120.

Daily Prep Problems

10/9: Read section 4.2. Do exercise 4.13 on page 101.
10/11: Read section 5.1. Do exercise 5.1 on page 112.
Be sure to test together-copies-of on two procedures such as + and stack.
HINT: Which is more appropriate, a base case of 0 copies or of 1 copy?
10/13: No daily.
10/16: Read section 5.2. Do exercise 5.4 on page 113.
10/18: Read section 5.3. Project 2 is due.
10/20: Break
10/23: Break
10/25: Read section 5.4. Do exercise 5.10 on page 121.
10/27: Read section 6.1-6.2. Project 3 is due.
10/30: Read section 6.3. Do exercise 6.5 on page 146.
11/1: Read section 6.4. Do exercise 6.11 on page 155.
As always, be sure to test your procedures.
11/3: Read section 7.1, 7.2. HW 5 due.
11/6: No daily. Review/catch up.
11/7: Exam #2