|
CS105 03 : Midterm II
0. Your name (0 points if correct, -100 points if not completed)
1. What does the following piece of code do? Do not give an
english
description of the procedure; this is a simple and function which
you should be able to express in 6 words or less. (10 points)
(define (mystery x y)
(cond ((= y 0) 1)
((> y 0) (* x (mystery x
(- y 1))))
((< y 0) (* (/ 1 x)
(mystery
x (+ y 1))))))
2. Write three functions which will return a solution to the following
problem.
a. The first function should use basic syntax (no lambda or lets) (5
points)
b. The second function should use a lambda procedure (10 points)
c. The third function should use a let statement (10 points)
Your substitution should be logical and GREATLY simplify
the expression. You will lose credit for an inappropriate substitution
f(x,y) = x2y2+(6x+10)y2 +4y +4
3. For this question, write 2 procedures which calculate x + y by
only adding or subtracting 1's from the answer.
a. The first should calculate it recursively (7.5 points)
b. The second should calculate it iteratively (7.5 points)
4. Rsort is an algorithm which takes a list and sorts its elements as
follows: it checks the length of the list. If the list has length 1, it
returns the list (it is sorted by it's very nature). If it is longer than
1, it finds the minimum element of the list, and appends that element to
Rsort called on the rest of the list.
a. Write a full procedure to perform rsort. (15 points)
b. Give asymptotic estimates of the space and time complexity for your
function (10 points)
5. x is a fixed point of the function x if f(x) = x. It is sometimes
possible to identify a fixed point by beginning with a guess and applying
f repeatedly: f(x), f(f(x)) f(f(f(x))) ... until we reach some value which
does not change much in successive applications of f.
a. Write a fixed point procedure which takes 3 arguments: a procedure
f, a guess x, and a tolerance value(how close our estimation must be to
the actual value. Note: recall the golden ratio function discussed in
class).
(20 points)
b. Write a call to your fixed point procedure which estimates y where
y = sin(y) + cos (y). sin and cos are both built in functions to the
language.
(5 points)
| 
