AP CS Midterm #1
0. (0 points) NAME___________________________________ PERIOD _______
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:
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 π2/6, not π.
Write the function euler-pi in terms of accumulate by filling in the blanks.
I think this is perhaps easier if we write an euler-term helper function and use it in euler-pi:
(define (euler-term n) (/ 1 (* n n)))
(define (euler-pi terms) (sqrt (* 6 (accumulate + 0 euler-term 1 (lambda (x) (+ x 1)) n))))