CS1 -- Fall 2008 -- Lab 2

CS 1 Fall 2008

Lab 2: Reduce to previously solved problem...

Assigned: Monday, October 6, 2008
Due: Thursday, October 16, 2008, 02:00:00

You should read through the end of Section 1.2.2 in SICP in order to be fully prepared for this lab.

Once again, in this lab make sure you use the "Intermediate Student with Lambda" language level in DrScheme. For the substitution model evaluations, you are encouraged to use the stepper to guide you, but again you will need to write up some trivial steps that the stepper skips over.

Part @: Time Synopsis

As you answer the problems below, make a note on how long you spent on each of the sections.
If any of the individual problems took you notably more time than the rating stated, please identify them and write down your actual time spent. This will help us calibrate future problem sets.

Part A: Exercises

Please attempt the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.

[20] Walk through the evaluation of the following code step by step using the substitution model. To save time, we will allow these shortcuts:
- writing e.g. + ==> + instead of + ==> [primitive procedure +]
- writing e.g. (lambda (x) ...) ==> itself instead of copying the entire lambda expression
- reducing single combinations which involve only numbers and primitive procedures in one step
  e.g. (= 2 0) ==> #f and (- 2 1) ==> 1.
  Note that if there are variables in the combination e.g. (+ 2 x) then you have to evaluate it explicitly.
However, aside from these shortcuts, do not skip any steps. In particular, we want you to explicitly evaluate all numbers, all defines, and explicitly desugar function definitions which don't use lambdas.

NOTE: These guidelines apply for the other substitution model problems in this lab as well.
```
(define incval 2)
(define (r arg c)
  (if (= arg 0) 
      c 
      (r (- arg 1) (+ c incval))))
(r 2 0)
    
```
Identify the kind of process that this represents.
[45] Using only the Scheme mathematical functions {+, -, <, >, =} and the if special form (but not *):
1. Write a function that performs multiplication on two non-negative integers recursively. We will do this in several steps.
  1. Write out the contract for the function, a one-line comment describing what it does, and a template for the function (which is just (define (name-of-function arg1 arg2) ...) with the appropriate substitutions of names; the ... should literally be in the function in place of the function body). We will fill in the details as we go.
  2. Now replace the ... placeholder with the first part of the function, which is the code to handle the base case(s). Here we only need one base case, though we could have other ones if we really wanted to. Leave the rest of the function (the recursive case) empty by using a new ... placeholder.
  3. Now, assuming that you want to change a by subtracting 1 in each recursive call, write the recursive step and complete the function. Write tests using check-expect to test both the base case and the recursive case.
  The point of this exercise is to get used to developing functions in stages: first write the contract, then a comment stating what the function does, then a trivial template for the function, then the base cases, then the recursive case. Note that only the recursive case required any real thought (we hope!). Ideally, the tests should be written immediately after writing the function template.
2. Walk through the evaluation of your recursive multiplication using the substitution model on the arguments 2 3 [i.e. evaluation of (multiply 2 3)].
3. Write a function that performs multiplication on positive integers iteratively (i.e. using a linear iterative process instead of a linear recursive process). Use a helper function. Write contracts, comments and tests as usual. You don't need to write out the stages of development of your function as you did above; just write the final functions. Remember that you will need an extra argument in your helper function to hold the current state of the computation, but your recursive step will be tail-recursive i.e. it will not involve any pending operations.

Part B: Book Exercises

Please work the following exercises from the textbook:

[10] Exercise 1.4 (compound expressions as operators). You don't have to write out a full substitution model evaluation, but explain in words why the procedure works i.e. explain enough to convince us that you could do the full evaluation if you wanted to.
[30] Exercise 1.6 (if as special form)
[45] Exercise 1.12 (binary coefficients using recursion)
For exercise 1.12, the procedure should be callable like this: (pascal-coefficient level n) where level is the level of the triangle (starting from 0 for the first level), and n is the index of the coefficient in the level (also starting from 0).

Make sure you put in a contract, a comment, and tests as usual. This function has multiple base cases, so make sure you get them all and test for all of them. Write the tests before you write the function!

Part C:

[70] Write a Scheme function which uses recursion to compute the quotient resulting from dividing one positive integer by another positive integer (i.e. the answer, throwing away all fractional parts). You may use any of the arithmetic operators {+, -, <, >, =} and any other non-arithmetic Scheme operations which you have learned. [This is not necessarily an efficient division algorithm.]
1. What is the base case?
2. What is the reduction step? In other words, how can you express the problem in terms of the solution to a smaller problem of the same kind?
3. Prove the correctness of the reduction step. In other words, show that the reduction step you have just described really will compute the same value.
4. Provide Scheme code for the recursive computation that corresponds to the reduction step you described above. As always, make sure there is a contract, a comment, and tests that cover the base case(s) and the reduction step.
5. Identify the kind of process that this represents.
6. Prove that your recursive procedure will always terminate on any positive input. You do not need to give a mathematical proof; just describe in words why the procedure will always terminate.
1. [20] Write a function called sum-integers-in-range which sums all the integers between two given integer endpoints (including the endpoints). Here is the template for the function:
```
;; sum-integers-in-range: integer integer -> integer
;; This function sums the integers between m and n, including the endpoints.
(define (sum-integers-in-range m n)
   ...)
```
  Make sure you add the appropriate tests. Write this as a recursive procedure.
2. [10] Give an informal proof that your sum-integers-in-range function is correct by considering the base case(s) and the recursive case (reduction step) separately. How can you be sure that the function will terminate on all integer inputs?
In this problem we're going to write a function that enables us to compute the number e, the base of natural logarithms, which is equal to 2.7182818... We will do this by summing a part of an infinite series expansion which computes e: e = 1/0! + 1/1! + 1/2! + ... where n! is the factorial of n (which in turn is n * (n-1) * (n-2) * ... * 1). In this problem you do not have to write explicit tests, though you can if you want to.

We'll start out with the factorial function itself:
```
;; factorial: number -> number
;; This function computes the factorial of the input number,
;; which for a number n is equal to n * (n-1) * ... * 1.
(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))
```
1. [5] Write a simple function called e-term which takes a (non-negative) integer argument and computes that term of the infinite series expansion of e. Be careful with the contract here -- the result will not in general be an integer. This function is not recursive.
2. [20] Write a recursive function called e-approximation that takes one positive integer argument and computes an approximation to e by summing up that many terms of the infinite series expansion of e (actually, it'll sum up the first n+1 terms, since it starts at term 0 and ends at term n). Write the function as a linear recursive process. Use your e-term function to help you write this one.
  
  As always, before you start, identify what the base cases are and what the reduction step has to be. (You don't need to write your thought process up in your submission.)
3. [5] Compute an approximation to e by summing up to the 100th term of the infinite series expansion. Write down the answer that DrScheme gives you in a comment in your lab submission.

Part D: Good code, Bad code

For each of the following procedures, please answer:

What does the procedure do?
How hard was it to figure this out?
What characteristics of the code made it easy or difficult to decipher the intended operation?

[10]

(define (factor? candidate number)
   (define (factor-aux candidate number multiple)
      (if (<= multiple number) 
          (if (= (* candidate multiple) number) ;; definition of factor
              #t
              (factor-aux candidate number (+ multiple 1))) ;; try next larger number
          #f)  ;; (number + 1) * (anything >= 1) is definitely > number
       )
   (factor-aux candidate number 1))