Homework 2

Due: February 23, 2004

• Do exercise 2.7 on page 38.
• Exercise 2.x1: The following procedure is supposed to compute n² + n for any nonnegative integer n. The procedure has a bug in it, and the "proof" of its correctness has a corresponding error. Correct both the procedure and the proof. That is, show what change needs to be made to the procedure so that it computes n² + n for any nonnegative integer n, and show what change needs to be made to the proof so that it correctly shows that your modified version of the procedure indeed computes n² + n for any integer n >= 0. You are to leave the overall recursive form of the procedure intact; it is not fair to have your corrected version just do (+ (* n n) n).

  (define square-plus
    (lambda (n)
      (if (= n 0)
          0
          (+ n
             (square-plus (- n 1))))))
  

  Theorem: For any integer n >= 0, (square-plus n) evaluates to n² + n.

  Base case: If n = 0, the answer is given as 0, which is equal to 0² + 0, and so is the correct answer.

  Induction hypothesis: Assume that for any integer k with 0 <= k < n, (square-plus k) evaluates to k² + k.

  Inductive step: For n > 0, we see by inspection of the code that (square-plus n) adds n to whatever (square-plus (- n 1)) evaluates to. Because n > 0, we have 0 <= n-1 < n, and so we can apply the induction hypothesis, substituting (n-1) for k. This tells us that (square-plus (- n 1)) evaluates to (n-1)²+(n-1). Doing the algebra,

  (n-1)2+(n-1)	= n2 - 2n + 1 + n - 1
  	= n2 - n

  This is very nearly our desired answer, with the only difference being that we want +n on the end. This explains why we add n to get the right answer.

  Conclusion: Therefore, by induction on n, we conclude that for any integer n >= 0, (square-plus n) evaluates to n² + n.

• Exercise 3.x1: Suppose we take a nonnegative integer, such as 314159, and we number the digits from right to left. For example, digit number 2 of 314159 is 5 because the second digit from the right is 5. We would like a procedure, digit-number, so that (digit-number 2 314159) would evaluate to 5. Similarly, (digit-number 6 314159) would evaluate to 3 (the sixth digit from the right). Of course, the integer whose digits we are interested in needn't be 314159; for example, (digit-number 3 1271) would evaluate to 2.
  1. Fill in the blanks in the following procedure definition. You may assume both arguments are legal; the position is at least 1, and the integer is not negative.

     (define digit-number
       (lambda (position integer)
         (if ______________________
             (remainder integer 10)
             (digit-number (- position 1) ____________________________))))
     

  2. Does this procedure generate a recursive process or an iterative process? Justify your answer.
• Do exercise 3.19 on page 72.