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

Solutions in RED.

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?


                       *                                    ; op


                       1                                    ; id


                       (lambda (x) x)                       ; term


                       a                                    ; a


                       1+                                   ; next


                       b                               ))   ; 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.)

1. 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.
   
   
2. Logarithmic: O(log₂n)
   We can rule this out because there is nothing in the code that chops n in half.
   
   
3. Linear: O(n)
   We can rule this out because the line containing recursive call contains more than one recursive call.
   
   
4. Exponential: O(xⁿ) 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.