AP CS Midterm #1

0. (0 points) NAME___________________________________ PERIOD _______

INSTRUCTIONS

• Write your name on the test. If you can't remember your name, it will cost you a point.
• This test is closed book. No computer, no friends, no Internet. Just you, your brain, your pen(cil), and the paper.
• Calculators are not permitted. Not even the really big calculators in the classroom.
• Where possible, SHOW YOUR WORK! (It is really hard to give partial credit if you don't!)
• Do not write programs that worry about checking for errors. You may assume that all arguments to a function will be in the function's domain.
• You can always write helper functions unless explicitly indicated otherwise.
• Don't panic. It's just a test.

Given the following definitions:

(define (square x) (* x x))
(define (identity x) x)
(define (1+ x) (+ x 1))

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (lambda (x)
    (cond ((= n 0) x)
          (else ((repeated f (- n 1)) (f x))))))

(define (filtered-accumulate pred? op id term a next b)
  (cond ((> a b) id)
        ((pred? a)
         (op (term a) (filtered-accumulate pred? op id term (next a) next b)))
        (else (filtered-accumulate pred? op id term (next a) next b))))

1. (3 points; 1 point each) What will the outputs be for the lines of code, below?

I want you to type (or copy and paste) these into the interpreter yourself.

> ((repeated square 2) 5)




> ((compose square 1+) 5)




> (filtered-accumulate even? * 1 square 1 (lambda (x) (+ x 3)) 10)

2. (5 points in two parts) The function gcd takes two inputs that are both positive integers. gcd should return the greatest common divisor of the two numbers. It uses the following algorithm:

• If the remainder of the first number divided by the second number is zero, return the second number.
• Otherwise, call gcd with the second number as the first argument and the remainder of the first number and the second number as the second argument.

Here is an example of a traced example of (gcd 112 42):

>(gcd 112 42)
>(gcd 42 28)
>(gcd 28 14)
<14
14

2A. (2 points) Based on the output, we can tell whether this is a recursive process or an iterative process. Which process is this and how do you know?

Iterative. We don't see the expansion and contraction that comes with a recursive process. Also, the state of the process is maintained by the parameters.

2B. (3 points) Write gcd.

(define (gcd a b)
  (cond ((= b 0) a)
        (else (gcd b (remainder a b)))))

3. (7 points in two parts) Problem 1.30 from the homework. Consider the function sum:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

3A. (2 points) Scheme uses applicative-order evaluation, meaning all of the arguments to a procedure must be fully evaluated and plugged into the parameters before the procedure begins execution. The exceptions to this rule are special forms, one of which is if, which uses normal-order evaluation, where arguments are evaluated only when needed.

Suppose that if used applicative-order evaluation instead. Would it make any difference in terms of whether the sum function would work? Explain.

If if used applicative-order evaluation, then all three inputs would have to be fully evaluated before if could start. That includes the recursive call to sum, which in turn would need if to evaluate in order to complete. The result would be an infinite loop that never returns.

3B. (5 points) The sum procedure above generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:

(define (sum term a next b)

  (define (iter a result)

    (if (> a b)
        
        result

        (iter (next a) (+ (term a) result))))

  (iter a 0))

4. (5 points) Recall from class and Problem 1.32 in the book that the higher-order function accumulate can be written as follows:

(define (accumulate op id term a next b)
  (cond ((> a b) id)
        (else (op (term a)
                  (accumulate op id term (next a) next b)))))

The mathematician Leonhard Euler is credited with proving the following theorem:

Note that this is π²/6, not π.

Write the function euler-pi in terms of accumulate by filling in the blanks.

(define (euler-term n)
  (/ 1 (* n n)))

(define (euler-pi terms)

  (sqrt (* 6 

     (accumulate +
                 0
                 euler-term
                 1
                 (lambda (x) (+ x 1))
                 n))))