%new exam1 1/27/98 RJF

CS 61A Midterm \#1 ver0.91 --- February 9, 1998

Your name \underbar{\hskip 3in}

login:\qquad cs61a--\underbar{\hskip 0.5in} 

Discussion section number \underbar{\hskip 0.5in}

TA's name \underbar{\hskip 3in}

Look at the edge of your seat. Write
your ROOM, seat row and number. Your row number may not be visible
from where you sit, so we will help you later.
 \underbar{\hskip 0.75in}


This exam is worth 40 points, or about 13\% of your total course grade.
The exam contains XXX substantive questions, plus the following:

{\bf Question 0 (1 point):}  Fill out this front page correctly and
put your name and login correctly at the top of each of the following
pages.

This booklet contains XXX numbered pages including the cover page.  Put all
answers on these pages, please; don't hand in stray pieces of paper.
This is an open book exam.

{\bf When writing procedures, don't put in error checks.  Assume that you
will be given arguments of the correct type.}

Our expectation is that many of you will not complete one or two of these
questions.  If you find one question especially difficult, leave it for
later; start with the ones you find easier.



I certify that my answers to this exam are all my own work, and that
I have not discussed the exam questions or answers with anyone prior
to taking this exam.

If I am taking this exam early, I certify that I shall not discuss
the exam questions or answers with anyone until after the scheduled
exam time.

Your name \underbar{\hskip 2.5in} login cs61a--\underbar{\hskip 0.3in}

{\bf Question 1 (7 points):}


What will Scheme print in response to the following expressions?
%Assume
%that they are typed in sequence, so definitions affect later interactions.
If an expression produces an error message or runs forever without
producing a result, you may just say ``error''; you
don't have to provide the exact text of the message.  If the value of an
expression is a procedure, just say ``procedure''; you don't have to show
the form in which Scheme prints procedures.  Assume that no global variables
have been defined before entering these expressions, except where noted.

(word '(+ 2 3) (+ 2 3))

((lambda (x y z) (* 5 y)) 3  4 7)

; from ex. 1.32, p. 61
 (accumulate se '(hurrah) (lambda(x) (word 'hip x)) 1 (lambda(x)(1+ x)) 3)

((if 3 - *) 23 2)

(a b c)

(let ((a 5)(b c))
  (*  a a b ))

((lambda (+) (+ 3)) (lambda (*) (+ * 2) )) 

{\bf Question 2 (5 points):}

{ Write a function
{\tt subsequence}
that, given a function {\tt f} and a list or sentence
{\tt sen} of $n$ elements 
computes a new list of $n$ elements.
The first element is {\tt (f sen)} of the whole list.
The second element is {\tt f} applied to a list consisting
of all but the first element of {\tt sen}, etc.

That is if {\tt sum}, defined below, adds up all the elements of a list,
 
(define (sum alist) ;; definition of sum
(if (empty? alist) 0 (+ (sum (bf alist)) (first alist))))

then
{\tt (subsequence sum '(7 9 3 5))} returns {\tt (24 17 8 5)}.


{\bf Question 3 (5 points):}

True or false?

\tick A $\Theta(\log(n^2))$ algorithm is faster than a $\Theta(2\log(n))$ algorithm.

\tick For small size inputs the $\Theta$ order of an algorithm more useful
than for large inputs.

\tick If $f(x)$ is $\Theta(\log x)$, then $\lim_{ x\rightarrow \infty}  f(x)/(\log x)$ is a finite constant.

\tick If {\tt f} is defined as

(define (f x) (* x x x)) }
Then an applicative-order evaluation of {\tt (f (g y))} evaluates {\tt (g y)}
more often than a normal-order evaluation.

\tick Function {\tt g} below
defines a linear iterative process:
(define (g a b c) (if (> a b) c (+ c (g (+ a 1) (- b 1) (+ c 1)))))}

Your name \underbar{\hskip 2.5in} login cs61a--\underbar{\hskip 0.3in}

{\bf Question 5 (8 points):}

{A polynomial can be represented as a sentence, where the words are the coefficients
of the terms.  The first element of the sentence represents the term of degree 0 
(the constant term), the second represents the term of degree 1, etc.
So, for example, $3 x^2+ 2 x +1$ would be {\tt '(1 2 3)} and $27 x^8 + 1$ would be 
{\tt '(1 0 0 0 0 0 0 0 27)}


  Write a function {\tt add-polys} that takes two polynomials each of arbitrary degree
each represented as a sentence and returns their sum, represented as a sentence.

Write a function term-multiply-poly that takes a polynomial of arbitrary degree represented
as a sentence,  a term coefficient and the degree of a term and returns 
the product represented by a sentence.

So, for example, if I wanted to multiply $9 x^2 + 2 x + 1$ by $7 x^3$, I would do:
>(term-multiply '(1 2 9) 7 3)
(0 0 0 7 14 63)

 Your name \underbar{\hskip 3in} login cs61a--\underbar{\hskip 0.5in}

{{\bf Question 6 (5 points):}

Write a procedure {\tt interleave} that takes two sentences  $s_1$  and $s_2$ as its arguments. It returns the sentence whose elements are alternate elements of $s_1$ and $s_2$ 
beginning with the first (the first of $s_1$, the first of $s_2$,
the second of $s_1$, the second of $s_2$, and so on).  If one sentence is longer than
the other, it behaves as if the shorter sentence was padded with 0's

For example,

> (interleave '(1 2 3 4) '(5 6 7 8))
(1 5 2 6 3 7 4 8)
> (interleave '(9) '(10))
(9 10)
> (interleave '(9) '(10 11 12))
(9 10 0 11 0 12)
> (interleave '(1 2 3 4) '(5))
(1 5 2 0 3 0 4 0)

}}

{\bf Question 6 (5 points) :}

{ Write a function
{\tt decapitate}
that, given a function {\tt f} of one argument returns a new
{\it function\/ } of one argument that returns the same value as {\tt (f x)},
except the value is {\tt butfirst} of what {\tt (f x)} would return.

That is, if

(define foo (decapitate square))

>(foo 8) 
4   ; because (bf 64) is 4

}

{\bf Question 5 (12 points) OLD:}
 If you understand {\tt accumulate} this should be easy.

Sometimes you want to {\tt reduce} a collection of elements by operating
on them in pairs, starting from the right, and given an end-value when
there is no element of the collection left. 
For example {\tt (reduce + '(2 5 6) 0)}
is meant to compute {\tt (+ 2 (reduce + '(5 6) 0))} which is, in turn, equivalent
to {\tt (+ 2 (+ 5 (reduce + '(6) 0)))} which is  {\tt (+ 2 (+ 5 (+ 6 (reduce + '() 0)))} which is {\tt (+ 2 (+ 5 (+ 6 0)))}
or 13.

You may need a few extra ``helper'' procedures. to complete these programs.
Use the reverse of this page if you need more space.


A. Define the procedure {\tt (reduce f s e)} illustrated
above that takes as its argument another
procedure {\tt f}, a  sentence {\tt s}, and an end-value {\tt e}. 
Procedure {\tt f} should take two arguments.


B. Use {\tt reduce} to reverse the order of words in a sentence. That is,
define a procedure {\tt reverse-by-reduce} that given
{\tt (hello good bye)} returns {\tt (bye good hello)}.


C. Use {\tt reduce} to find a word with the largest number of
letters in a given sentence. That is, define a procedure
{\tt longest} that given {\tt (two three five)} returns {\tt three}.


D. Use {\tt reduce} to find the minimum number in a given
sentence {\tt r}. That is, define a procedure
{\tt minimum} that given {\tt (0 -500 30)} returns {\tt -500}.
If {\tt r} is empty, return the word {\tt error}.