Note: This test ended up being way too short; there will be an additional programming problem to replace problem 1

**AP
Computer Science Test #1**

**0. (0 points) NAME________________________________________ PERIOD_________**

__INSTRUCTIONS__

- Put your name on the test.
**Failure to do so will result in a loss of one point.**(Let's face it, if you don't know your name, you probably have bigger problems than this test.) - This test is
**closed book**. Your monitor should be turned off. It’s you, your brain, your pencil, and the test. - Friends are not permitted, either.
- Where possible,
**SHOW YOUR WORK!**I don’t know how to assign partial credit to the void. - When asked to write a function, do not do error checking. You may assume that when the function is called, it will only be called with legal arguments.
- You can always write helper functions if you want.
- Don't panic. It's just a test.

**1. (5 points) **Given:

(define (square x) (* x x)) (define (1+ x) (+ x 1)) (define (identity x) x) (define (accumulate op id term a next b)

(cond ((> a b) id)

(else (op (term a)

(accumulate op id term (next a) next b)))))

What will be printed for each expression, below? If the expression will produce an error, write ERROR.)

> (* (+ 6 5) (- 7 4))33> ((if sqrt 1+ identity) 9)10> ((lambda (x y z) (y z x)) 13 - 6)-7> (define (mystery a b) (accumulate * 1 identity a 1+ b)) (mystery 3 6)360> (define (mystery2 a b)

(accumulate cons '() square a (lambda (x) (+ x 2)) b)) (mystery2 1 5)(1 9 25)

**2. (5 points) **The function `filtered-accumulate` is written as follows:

(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))))

The function `product-of-perfect-squares` takes two inputs, a lower bound and upper bound, and produces the products of all numbers between those numbers that are perfect squares. Here are a some examples:

> (product-of-perfect-squares 1 12) ; will produce 1 * 4 * 9 = 36 36 > (product-of-perfect-squares 0 4) ; 0 * 1 * 4 = 0 0 > (product-of-perfect-squares 3 28) ; 4 * 9 * 16 * 25 = 14400 14400

Write `product-of-perfect-squares` in terms of `filtered-accumulate` by filling in the blanks, below. The parameters to which the blanks correspond are indicated in the comments on the right.

**You MUST fill in the blanks to get credit on this problem. Alternative solutions, such as writing product-of-perfect-squares from scratch, are not what is being measured on this problem. You can write helper functions if you desire.**

Scheme contains the functions `sqrt` and `integer?` which you may find useful on this problem.

(define (product-of-perfect-squares a b) (filtered-accumulate(lambda (x) (integer? (sqrt x))); pred?*; op1; id(lambda (x) x); terma; a1+; nextb)) ; b

**3. (5 points) **(Problem 1.16 from the book) The procedure `fast-expt` is given in the book as
follows.

(define (fast-expt b n)

(cond ((= n 0) 1)

((even? n) (square (fast-expt b (/ n 2))))

(else (* b (fast-expt b (- n 1))))))

This is a recursive process. Rewrite it as an iterative process. Below is a little bit of code to help you get started; you need to fill in fast-expt-iter.

(define (fast-expt b n) (fast-expt-iter 1 b n)) (define (fast-expt-iter a b n) ; You write code below(cond ((= n 0) a) ((even? n) (fast-expt-iter a (square b) (/ n 2))) (else (fast-expt-iter (* a b) b (- n 1)))))

**Note that a * b^n is a loop invariant (i.e., it remains constant throughout the iterative process of producing a result).
**

)

**4. (5 points in three parts) **The following function computes powers of 2:

(define (2-to-the n)

(2-to-the-n-helper 1 n))

(define (2-to-the-n-helper result n)

(cond ((= n 0) result)

(else (2-to-the-n-helper

(+ result (2-to-the-n-helper 1 (- n 1)))

(- n 1)))))

**4A. (1 point)** Which of the following best describes the growth of this function? (Circle one.)

- Constant: O(1) (the amount of time to compute is independent of n)

**We can rule this out because the bigger n is, the more computation is required to reach a solution.**

- Logarithmic: O(log
_{2}n)

**We can rule this out because there is nothing in the code that chops n in half.**

- Linear: O(n)

**We can rule this out because the line containing recursive call contains more than one recursive call.**

**Exponential: O(x**^{n}) where x > 1

**A recursive call inside of a recursive call? Unless 2-to-the-n-helper hits its base case, there will be more than one additional recursive call.**

**4B. (2 points)** Explain why your choice makes sense.

**Explanation given above.**

**4C. (2 points)** Is `2-to-the-helper` a recursive or iterative process? Explain. (Points will be awarded based on the explanation.)

**It is a recursive process. There are functions that must persist in memory while the inner 2-to-the-n-helper is computed.**