%%%%%%
%%%%%%
%%%%%% Modified by A. Coates
%%%%%%
%%%%%%
%%%%%%
%%%%%%

%%%%%%%%%%%
% exam1 Allison Coates 
% Version 0.1 
% Test Date: 6 July 2001.



 UNIVERSITY of CALIFORNIA at Berkeley\\
Department of Electrical Engineering and Computer Sciences\\
Computer Sciences Division\\


CS 61A Summer Session 2001 \\
Midterm \#1\\
July 6, 2001\\

Your name \underbar{\hskip 3in} 

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

Section number \underbar{\hskip 0.5in}

\vspace{.2in}

TA's name \underbar{\hskip 3in}
\end{large}
\end{center}


This exam contains 6 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 7 numbered pages including the cover page.  Please put all
answers on these pages. Don't hand in stray pieces of paper.
This is an open book/open note exam. Use of computers or calculators is prohibited.

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

This exam is worth 40 points, or about 13\% of your total course grade.
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. You have two hours to complete this test.


By signing below, you certify that your answers to this exam are all your
own work, and that you have not discussed the exam questions or answers with anyone prior
to taking this exam.
\begin{center}

Signature: \underbar{\hskip 2.5in}


{\bf Question 1 (6 points):}
%% part a: 2 Lambda
%% part b: 1 DA
%% part c: 1 DA
%% part d: 2 Lambda


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 Scheme's primitives.




\noindent {\bf 1a.}
{\prgex%
$>$ ((lambda (x y) (* x (y)))  5 (lambda () (+ 1 8))) 


}
%% part a: 2 points. 


%point: lambda can take lambda as an argument
%%answer: 
%%45 
%% Part a: no partial credit  
\noindent {\bf 1b.}
{\prgex%
%%     $>$ (first (butlast (se '1 '(2 3) '(4 5 '(6)) 6))) 
%%%save for later when lists are defined
$>$ (define p (cons (cons 1 2) (cons 3 4)))
$>$ (cadr p)



}
%% part b: 1 point 
%point: cadr is (car ( cdr p) meaning the car of the cdr of p, not cdar
%answer: 
% 3
%% no partial credit 
\noindent {\bf 1c.} 

{\prgex%
$>$ (butfirst (first (butlast (se  '(once upon a time)))))


}
% 1 point 
%point:  first/bf/bl work on words AND sentences.
%sentences are weird amalgams of data.
%answer: nce
% Part a: no partial credit
% Common mistakes:
%  (1) Thinking "se" requires at least 2 arguments


\noindent {\bf 1d.}
{\prgex%
$>$ (define (foo func start sent)
     (cond ((empty? sent) 'yes)
           ((equal? (func start) (first sent)) (foo func (+ 1 start) (bf sent)))
           (else sent)))
foo
$>$ (foo  (lambda (x) (* 2 x)) 1 (se 2 4 6))

}

\vfill\eject
%%point: how to invoke a lambda and see the recursion at work
%% Total 2 points
%%%answer: yes
%%Partial Credit: 1 point for incorrectly writing 'yes or (yes).


{\bf Question 2 (9 points):}

Ben Bitdiddle wants to buy donuts for himself and his homework partner Alyssa. The store sells
{\tt cream}, {\tt jelly}, and {\tt glazed} donuts.

To see if he has enough money, 
Ben wants to make a function that calculates the cost of their order. 
He puts their orders into a sentence form. 
For example, given the following orders:
{\prgex%
  Alyssa wants 15 jelly, 8 glazed.
  Ben wants    20 jelly, 4 cream.
}

The sentence is {\tt (se '15jelly '8glazed '20jelly '4cream)},  
where each word is a concatenation of the amount and the type of donut. 
That is,  {\tt '20jelly} means 20 jelly donuts.  
The price (in dollars) per donut is:
{\prgex%
              cream: 3;        jelly: 2;        glazed: 1
}


\begin{itemize}
%2 points 
\item [2a.] Assume someone has written the selector {\tt type-donut} for you,
which returns a word corresponding to the type.
Write the selector  {\tt num-donut}, which returns a number. 
Selectors take one argument, a word, which is a concatenation 
of the amount and the type of donut.
\vspace{1.0in} 
%% part a: 2 points:
%% lots of possible solutions. in my mind, it's easiest to use
%% the type-donut selector. most of you didn't do that--that's too bad,
%% because that was really the point. Some of you wrote recursive
%% or iterative processes--which were okay, or technically correct. Some 
%% of you wrote technically correct code that did unnecessary string operations:
%% that is Entirely Not the point!


%% 
%% iterative: 
%%  (define (num-donut  dorder)
               ( define (helper dorder num name)
                        (cond ((equal? (type-donut dorder) name) num)
                                    (else (helper dorder (word num (first name))  (bf name)) )))
               (helper dorder " " dorder))

%% other reasonable solutions:
%% recursive:
%% (define (num-donut  dorder)
             (if (number? (last dorder)) dorder) (bl dorder))

%% this wasn't necessary, but if you care,
%%here's what the type-donut would have looked like:

%% (define (type-donut dorder)
%%        (if (number? (first dorder)) (type-donut (bf dorder)) dorder))



\item[2b.] %2 points RI
Is the function you wrote for {\tt num-donut} a recursive
process or an iterative process?

%% part b: 2 points
%% of course, this answer depends on the previous one.

\vspace{.5in} 
\item [2c.] %2 points FP

Write an additional procedure {\tt donut-cost} which takes a donut-type 
as an argument and returns the cost. 

%% part c: 1 pt 
%% A simple cond statement.
%% if part d is done right, this makes it a piece of cake.
%% (define (donut-cost dtype)
%%      (cond ((equal? dtype 'glazed) 1)
%%                  ((equal? dtype 'cream) 3)
%%                  ((equal? dtype 'jelly) 2)))

\vspace{1.0in} 
\item[2d.] % 2points DA 2 FP

Write a function {\tt how-much} that takes a sentence (in the form given above),
and calculates the total cost using the above abstractions. For example,
{\prgex%
$>$ (how-much (se '1jelly '1glazed '2jelly '3cream)) 
     16 

}
\end{itemize}

%%answer  
%% part d: 4 points. you were supposed to put it all together nicely.
%%
%% answer:
%% (define (how-much dsent) (+ (* (donut-cost (donut-type (first dsent))) (num-donuts (first dsent))) (how-much (bf dsent))))
%% Partial credit:
%% depending on answer, 1 point for correcty use of :
%% donut-cost, donut-type, num-donut, and recursive call to how-much.
\vfill\eject

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


{\bf Question 3 (4 points) }



Consider the definitions:
{\prgex%
(def (g x) 
    (+ 1 (f (g x))))

(def (f x) 0)

(def (h x) 
    (+ 1 (p (h x))))

(def (p x) (if (= x 0) 0 1))

}
\begin{itemize}
\item[3a.] What will happen if you type {\tt (g 3)} under applicative order evaluation?
%% 1 point
%% answer: 
%% Loop forever.
%% no partial credit

%% to see why it loops forever,
%% (g 3) gets replaced with (+ 1 (f (g 3)))
%% applic order means that the interpreter
%% attempts to evaluate (f (g 3)). To do so,
it evaluates the arguments to f, therefore, it evals (g 3)...
%% in the interpreter we see:
%%(g 3) ----> 
%%  (+ 1 (f (g 3)))
%%(f (g 3)) 
%% (g 3) ----> 
%% etc.

\item[3b.] What will happen if you type {\tt (g 3)} under normal order evaluation?
%%
%% 1 point
%% answer:
(g 3) ----> 
        (+ 1 (f (g 3)))
                 (f (g 3)) ----> 
              (+ 1 0) ==> 1
                1

%%the interpreter doesn't try to eval (g 3) when it's an argument to f,
%%not until it looks at the body of f.
%%since (g 3) isn't in the body, f just returns 1.

%% no partial credit
\item[3c.] What will happen if you type {\tt (h 3)} under applicative order evaluation?

%%
%% 1 point
%% answer: 
%% Loop forever.

(h 3) ----> 
       (+ 1 (p (h 3)))
               (p (h 3))
                    (h 3) ----> 
%% same explanation as part a.
%% no partial credit

\item[3d.] What will happen if you type {\tt (h 3)} under normal order evaluation?
%%
%% 1 point
%% answer:
%% Loop forever.
%% The reason is that eventually, it does need to evaluate the result of (h 3):
Originally, (h 3) is substitues into the body.
When the body contains (p (h 3)), normal order substitutes (h 3) into the body of p.
But the if statement requires that (h 3) be evaluated.
(h 3) ----> 
(+ 1 (p (h 3)))
        (p (h 3)) ----> 
             (if (= (h 3) 0) 0 1)
                   (= (h 3) 0)
                        (h 3) ----> 

%% no partial credit

\end{itemize}
\vfill\eject
Your name \underbar{\hskip 2.5in} login cs61a--\underbar{\hskip 0.3in}

{\bf Question 4 (10 points):}


In this question, you will provide a simple way to make a procedure which takes a sentence 
of numbers and returns a sentence of numbers with some of the values manipulated
and others untouched.

 For example, the created procedure might divide all
of the even numbers in a sentence by 2, or might take 
every prime number in a sentence and replace
 it with the smallest prime number greater than the one replaced.
\begin{itemize} 
\item[4a.]  %5 points lambda
 Write a general procedure {\tt make-num-manip}. 
{\tt make-num-manip} takes two arguments: a predicate {\tt pred} and a procedure {\tt manipulate}. 
{\tt pred} takes one number as an argument. {\tt manipulate} takes one number as an argument. 
{\tt make-num-manip}  must return a procedure which takes a sentence of numbers 
and returns a sentence of numbers such that if the predicate holds on that input, 
the output value is the manipulated input.

%% part a: 5 pt Lambda

%(define (make-num-manip pred manipulate) 
%  (lambda (sent) 
%    (cond ((empty? sent) '()) 
%          ((pred (first sent)) 
%           (se (manipulate (first sent)) 
%               ((make-num-manip pred manipulate) (bf sent)))) 
%          (else 
%           (se (first sent) ((make-num-manip pred manipulate) (bf sent))))))) 

%%  1 point for starting the definition correctly
%%  1 point for base case
%%  1 point for correctly returning a function that takes a
%%     sentence as argument
%%  1 point for handling correctly the case when the predicate is not
%%    satisfied
%%  1 point for handling correctly the case when the predicate is
%%     satisfied

%% using every worked as well.
%%  Common mistakes: 
%%    (1) Not returning a procedure
%%    (2) Starting the answer correctly as:
%%             (define (... ...  ...)
                    (lambda (sent)
                     ....
%%                ))
                  
%%        But then getting confused how to use recursion within the
%%        lambda.

%%    (3) Thinking that if the predicate is not satisfied, the
%%        element does not have to be included in the resulting sentence
%%    If you don't like this, tough; it was (a) in the question, and (b) in the example shown.

 
\vspace{1.4in} 
\item[4b.]  

%2 points

Write a procedure {\tt get-next-prime} which takes a number and returns
the smallest prime number greater than that number.
Here's an example:
{\prgex%
$>$ (get-next-prime 6) 
     7
     $>$ (get-next-prime 7) 
     11
}
Assume that there is a procedure {\tt prime?} which tests
whether or not a number is prime. Neglect efficiency concerns.
\vspace{1.4in}  

%%(define (get-next-prime num)
%%  (get-next-prime-helper (+ num 1)))

%%(define (get-next-prime-helper num)
%%  (if (prime? num)
%%      num
%%      (get-next-prime-helper (+ num 1))))

%%Partial Credit: 
%%  1 point for off-by-one error i.e. writing something like
%%         (define (get-next-prime n)
%%             (if (prime? n) n ...))
%%  instead of
%%       (define (get-next-prime n)
%%          (if (prime? (+ n 1) (+ n 1) ...))

%%  0 points if completely wrong.

%%  Common mistakes:  the off by one error.




\item[4c.]


Now write a procedure, {\tt replace-primes}, that takes a sentence of numbers
as an argument and returns that sentence with all of the prime
numbers in the old sentence replaced by the smallest prime greater than that number
 (as defined above). 
Here's an example: 
{\prgex%
$>$ (replace-primes '(2 6 7 9))
     (3 6 11 9)

}
%% part c: 3 points 
%% answer:
%% (define replace-primes (make-num-manip prime? get-next-prime))
%% or
%% (define (replace-primes sent)
%%  ((make-num-manip prime? get-next-prime) sent))

%% Part3:
%% There were basically 2 kinds of answers: using Part1 and
%% writing a recursive procedure from scratch.
%% you WERE SUPPOSED to use part 1, since it made it so simple.
  
%%  For those who used Part1:
%%   2 points for errors where they got this right:
%%    (define (replace-primes s)
%%        (make-num-manip ... ...))
  

%%  For those who did not use Part1:
%%  1 point for base case
%%  1 point for correctly handling the case when the first element
%%    is prime
%%  1 point for correctly handling the other case

%%   Common mistakes:
%%   (1) throwing away the element if it is not prime
%%   (2) saying (get-next-prime (+ (first s) 1)) instead of
%%       (get-next-prime (first s))




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

{\bf Question 5 (6 points) :}
You are a computer scientist consulting to 
a giant chain store BerzerkMart, that sell clothes, food, toiletries, sporting goods,
and automotive supplies. They want you to write a procedure
{\tt same-products? } that determines if two stores have the same set of products in their respective stores.
For simplicity, just ignore the number of items of that product.

Unfortunately, you don't know how their software keeps track of products. 
You don't even have a list of all the possible products.

You have available the following functions. Use some/all of 
them to write {\tt same-products?} which takes two stores as arguments
and returns true if the two stores have the same set of products in their stores.
\begin{itemize}
\item {\tt (amount x)  }which returns the number of items of product {\tt x}.
\item {\tt (overlap S T) }which returns the set (in no particular order) of products in both store {\tt S} and store {\tt T}.
\item {\tt (either S T) }which returns the set (in no particular order) of products in either store {\tt S} or store {\tt T}.
\item {\tt (is-in? x S) } which returns \#t if a product {\tt x} is in store {\tt S}.
\item {\tt (every-and f S)  }which applies the function {\tt f} to every product in store {\tt S} and returns the AND of those results.
\end{itemize}
You should use the fact that two stores have equal inventories
if every product in store S is in store T, and if every product in store T is in store S.

%% 6 points
%% (define (same-products? S T) 
%%           (and (every-and (lambda (x) (is-in? x S)) T)
%%                   (every-and (lambda (x) (is-in? x T)) S)))

%% Partial Credit:
%% 0 Points for violating the abstraction barrier. YOU DON'T KNOW the underlying
%% implementation, so you can' use car, cdr, member, list, sentence, first, etc. If you did,
%% you got nothing.

%% 2 points if you didn't follow the hint, but instead at least recognized
%% that you wanted to check if the intersection and union were equal. the problem
%% that {equal} is still an abstraction violation! this wouldn't work Either. but 
%% you received 2 points for getting that piece and not using any other more obvious DAVs.

%% 4 points if you had the procedures rights, but the (and) call wrong, or mis-used the lambda invocation,
%% but knew you needed one.

\vfill\eject

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

{\bf Question 6 (4 points) :}

Time efficiency questions. For each of the following function, decide its order of growth
in $\Theta()$ ``big-Theta'' notation:

\begin{itemize}

\item[6a.] 
 
with respect to n, where n is the number of words in sent 
{\prgex%

(define (bar? sent) 
  (cond ((empty? sent) \#f) 
        ((equal? (first sent) 'hi) \#t) 
        (else (bar? (bf sent))))) 

}


%%answer
%%;;O(n)
%% 2 points each. No partial credit.
\item[6b.] 

with respect to n, the number of words in sent       

{\prgex%

(define (baz sent) 
  (cond ((empty? sent) 0) 
        ((bar sent) (+ 1 (baz (bf sent)))) ;; bar is defined above in 6a
        (else (baz (bf sent))))) 

}
\underbar{\hskip 0.6in}
%%;;O(n^2)  
%% 2 points each. No partial credit.