% -*- Mode: Tex -*-

\input /homes/welg/6001/fall96/6001mac.tex

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\begin{document}

\psetheader{Fall Semester, 1996}{Quiz I}

\centerline{\bf Closed Book}

\vskip 10pt

Please write clear and concise answers to the questions in  the spaces
provided in this booklet.  You may use scratch paper if you need, but the
spaces we provide are the {\bf only} places we will look at when grading.

Write your name (1 point): \emptybox{4in}{.5in}

\vskip 10pt

Write ``your name'' (1 point): \emptybox{4in}{.5in}

\vskip 20pt

\centerline{
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\bf Circle Your Recitation Section}\\
\hline
Time & Instructor &T.A.\\
\hline
10&Rod Brooks&Becca Xiong\\
11&Rod Brooks&Mike McCandless\\
\hline
10&Pat LoPresti&Jay Ongg\\
11&Pat LoPresti&Jane Chang\\
\hline
11&Pam Lipson&Josh Tauber\\
12&Pam Lipson&Daniel Coore\\
\hline
1&Nir Shavit&Anthony Kam\\
2&Nir Shavit&Paul Van Eyk\\
\hline
\end{tabular}
}


Please do not write below this line:

\vskip 10pt

\hrule

\vskip 10pt


\begin{tabular}{|c|c|c|c||c|c|c|c|}
\hline
Problem & Value & Grade & Grader &Problem& Value & Grade &Grader \\
\hline
0& 2 & & &5&10& &\\
\hline
1& 14 & & &6 &18& & \\
\hline
2& 5& & &7&10& &\\
\hline
3& 10& & &8&15& &\\
\hline
4& 16& & &Total&100 & &\\
\hline
\end{tabular}


\newpage

{\bf Question 1 {\bf (14 points)}:}

For each of the following expressions or sequences of expressions,
circle the letter for the statement that best describes the result of
evaluating the final expression in each set.  Treat each set as
independent of the others.

\begin{enumerate}

\item {\tt (* (+ 2 3) 4)}

\begin{enumerate}

\item evaluates to 9

\item evaluates to 20

\item evaluates to 24

\item returns an error

\end{enumerate}

\item {\tt (/ (+ 2 3 4) (if 0 (* 3 1) 9))}

\begin{enumerate}

\item evaluates to 1/3

\item evaluates to 3

\item evaluates to 1

\item is an error

\end{enumerate}

\item {\tt (define (x y) 1)}

\begin{enumerate}

\item  is equivalent to {\tt (let ((x y)) 1)}

\item  is equivalent to {\tt (define x (lambda () y 1))}

\item  is equivalent to {\tt (define x (lambda (y) 1))}

\item is an error

\end{enumerate}

%\item \begin{lisp}
%(let ((a 5))
%  (* a 2))
%\end{lisp}
%
%\begin{enumerate}
%
%\item evaluates to 5
%
%\item evaluates to a procedure
%
%\item is equivalent to {\tt ((lambda (a) (* a 2)) 5)}
%
%\item is an error
%
%\end{enumerate}

\item {\tt (lambda (x) 5)}

\begin{enumerate}

\item  evaluates to 5

\item  evaluates to a procedure

\item associates variable {\tt x} with 5

\item  is equivalent to {\tt (let ((x 5)) x)}

\item is an error

\end{enumerate}

\newpage

\item \begin{lisp}
(let ((x 1))
  (let ((x 5)
        (y (+ x 2)))
    (+ x y)))
\end{lisp}

\begin{enumerate}

\item  evaluates to 8

\item  evaluates to 12

\item  evaluates to 4

\item  evaluates to a procedure

\item is an error

\end{enumerate}

\item \begin{lisp}
((lambda (+ x y) (x + y)) 3 * 4)
\end{lisp}

\begin{enumerate}

\item evaluates to 7

\item evaluates to 12

\item evaluates to a procedure

\item is an error

\end{enumerate}
 
           
%7. ((lambda (a b c) (b + c)) 
%    (lambda (c d e) (d e))
%    1)
%  a. evaluates to 1
%  b. evaluates to 2
%  c. evaluates to a procedure
%  d. is an error

\item  {\tt (if (eq?\ 'a (quote a)) (lambda (x) 1) 2)}

\begin{enumerate}

\item evaluates to 2

\item  evaluates to 1

\item  evaluates to a procedure

\item  is an error

\end{enumerate}

%\item {\tt (cons 'x '())}
%
%\begin{enumerate}
%
%\item creates a list with one element
%
%\item creates a list with two elements
%
%\item prints as {\tt (x . ())}
%
%\item is an error
%
%\end{enumerate}

%\item {\tt (eq? (cons 'a '()) (list 'a))}
%
%\begin{enumerate}
%
%\item evaluates to \#t
%
%\item evaluates to \#f
%
%\item evaluates to {\tt a }
%
%\item evaluates to the value of {\tt a}
%
%\end{enumerate}


%11. (define (foo x) (+ x 1))
%   (define (bar y) (y 5))
%   ((bar foo) 2)
%  a. evaluates to a procedure
%  b. evaluates to 3
%  c. evaluates to 6
%  d. evaluates to 5
%  e. is an error
%

\item \begin{lisp}
(define (square x) (* x x))
((lambda (y) ((lambda (z) (y z)) 4)) square)
\end{lisp}

\begin{enumerate}

\item evaluates to a procedure of 1 argument, {\tt y}

\item evaluates to a procedure of 1 argument, {\tt z}

\item evaluates to 16

\item is an error

\end{enumerate}

\newpage

\item \begin{lisp}
(define x (list 10 20))
(cond ((null? (cdr x)) 1)
      ((= 20 (cdr x)) 2)
      (else 3))
\end{lisp}

\begin{enumerate}

\item evaluates to 1

\item evaluates to 2

\item evaluates to 3

\item evaluates to \#f

\item is an error

\end{enumerate}

\item \begin{lisp}
(define (weave a b)
  (lambda (x) (b (a (b (a x))))))
\null
((weave (lambda (x) (* 2 x))
        (lambda (x) (* x x)))
 1)
\end{lisp}

\begin{enumerate}

\item evaluates to 8

\item evaluates to 32

\item evaluates to 64

\item evaluates to some other number

\item is an error

\end{enumerate}


\item \begin{lisp}
(define (identity x) x)
\null
(define (compose f g)
  (lambda (x) (f (g x))))
\null
(define (repeated f n)
  (if (= n 0)
      identity
      (compose f (repeated f (- n 1)))))
\null
(define (square x) (* x x))
\null
((repeated square 3) 2)
\end{lisp}

\begin{enumerate}

\item evaluates to 8

\item evaluates to 36

\item evaluates to 64

\item evaluates to 256

\item is an error

\end{enumerate}

\end{enumerate}

%13. (define (foo x)
%      (lambda (y) (+ x y)))
%    (define x 1)
%    ((foo 2) x)
% a. evaluates to 3
% b. evaluates to 4
% c. evaluates to a procedure
% d. is an error      
      

\newpage

\centerline{\fbox{\bf You can detach this page for easy reference, if you like}}

\vskip 10pt

We are going to build a simple database system to keep track
of votes by precinct for the presidential election.  Each data
structure for a precinct is built by using the following
constructor:

\begin{lisp}
(define (make-precinct name registered votes)
  (list 'precinct name registered votes))
\end{lisp}

with associated selectors 

\begin{lisp}
(define precinct-name ??)
(define registered ??)
(define votes ??)
\end{lisp}

The heart of the precinct structure is a separate {\it votes} data
structure that keeps track of the votes for each candidate:

\begin{lisp}
(define first-entry car)
(define rest-entries cdr)
(define add-entry cons)
(define empty-votes? null?)
(define empty-votes '())
\end{lisp}

And finally, an actual entry in the votes structure is constructed
using

\begin{lisp}
(define (make-entry candidate-name tally)
  (cons candidate-name tally))
\end{lisp}

with associated selectors

\begin{lisp}
(define candidate ??)
(define tally ??)
\end{lisp}

An example of constructing a precinct structure is:

\begin{lisp}
(define p1 (make-precinct 'diamond
                          15293
                          (add-entry
                              (make-entry 'clinton 6291)
                              (add-entry (make-entry 'dole 4320)
                                         empty-votes))))
\end{lisp}

Here is another example:

\begin{lisp}
(define p2 (make-precinct 'estabrook
                          20913
                          (add-entry
                              (make-entry 'dole 5120)
                              (add-entry (make-entry 'clinton 4813)
                                         (add-entry (make-entry 'perot 143)
                                                    empty-votes)))))
\end{lisp}

\newpage


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

Finish the implementation of our data abstractions by completing
the following:

\begin{lisp}
(define precinct-name \emptybox{5in}{.5in})
(define registered  \emptybox{5in}{.5in})
(define votes  \emptybox{5in}{.5in})
\end{lisp}

\begin{lisp}
(define candidate  \emptybox{5in}{.5in})
(define tally  \emptybox{5in}{.5in})
\end{lisp}

\newpage

{\bf Question 3 {\bf (10 points)}:}

Draw a box and pointer diagram that represents {\tt p1}.

\emptybox{6.5in}{4in}

\newpage

{\bf Question 4 {\bf (16 points)}:}

We want a procedure {\tt precinct-total} that sums the number of
votes cast in a given precinct:

\begin{lisp}
(precinct-total p1) ==> 10611
\end{lisp}

Suppose you are a user of the precinct and entry abstractions, but know
nothing of the implementation given above.  You are to implement the
procedure {\tt precinct-total}, and to be very careful to 
make no assumptions about the underlying implementation.  

Part A. 

Using the data abstractions specified above, write a linear recursive
implementation of {\tt precinct-total}.  That is, if $n$ is the number of
candidates (entries) in the precinct {\it votes} structure, write a
procedure  {\tt precinct-total} that is $\Theta(n)$ in the number of steps
(time) required, and $\Theta(n)$ in the deferred operations (space)
required.

%Ans:
%
%(define (precinct-total precinct)
%  (define (votes-summary votes)
%    (if (empty-votes? votes) 
%        0
%        (+ (tally (first-entry votes))
%           (votes-summary (rest-entry votes)))))
%  (votes-summary (votes precinct)))


\emptybox{6.5in}{4in}

\newpage

Part B. 

Again using the data abstractions specified earlier and making no
assumptions about the underlying representation, write a linear
iterative implementation of {\tt precinct-total}.  That is, if $n$ is
the number of candidates (entries) in the precinct votes structure,
write a procedure {\tt precinct-total} that is $\Theta(n)$ in the number of
steps (time) required, and $\Theta(1)$ in the deferred operations
(space) required.

%Ans:
%
%(define (precinct-total precinct)
%  (define (votes-summary votes so-far)
%    (if (empty-votes? votes) 
%        so-far
%        (votes-summary (rest-entry votes)
%                       (+ (tally (first-entry votes)) so-far))))
%  (votes-summary (votes precinct) 0))


\emptybox{6.5in}{4in}

\newpage

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

Recall the following definitions from lecture and from the
notes:

\begin{lisp}
(define (accumulate op init lst)
  (cond ((null? lst) init)
        (else (op (car lst) (accumulate op init (cdr lst))))))
\null
(define (filter pred lst)
  (cond ((null? lst) '())
        ((pred (car lst)) (cons (car lst) (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))
\null
(define (map proc lst)
  (if (null? lst) 
      '()
      (cons (proc (car lst)) (map proc (cdr lst)))))
\end{lisp}

Now assume that we are to implement {\tt precinct-total} as part
of the data abstraction, so that we know that the votes data
structure follows the conventions of list data structures.
Using {\tt accumulate, map}, and/or {\tt filter}, implement {\tt
precinct-total}:

%Ans:
%
%(define (precinct-total precinct)
%  (accumulate + 0 (map tally (votes precinct))))
%

\emptybox{6.5in}{3in}

\newpage

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

Suppose we want to maintain the {\tt votes} structure part of our
system in sorted order, with the candidate with the most votes first.
You are to write a procedure {\tt insert} which takes as arguments an
entry (e.g., something built by {\tt make-entry}) and a current set of
votes in sorted order (e.g., something built by using {\tt add-entry},
as in {\tt p1} but in decreasing order), and returns a {\tt votes}
structure with the {\tt entry} inserted in the correct place.

\emptybox{6.5in}{3.5in}

Using the procedure you have created, we can convert an old {\tt
votes} structure with entries in arbitrary order into a new structure
with the entries sorted.  In particular, we can successively insert
elements from the old version into a new version.
Complete the definition below to accomplish this.

\begin{lisp}
(define (insert-all old-votes)
  ;; assume that old-votes is a structure built using add-entry
  (define (helper todo done)
     \emptybox{5.5in}{2in}
    )
  (helper old-votes empty-votes))
\end{lisp}

\newpage 

{\bf Question 7 {\bf (10 points)}:}

Suppose we have a tree (defined as a list of lists) which can contain
either numbers or symbols.  We would like to check if the tree
contains only symbols at the leaves.  For example

\begin{lisp}
(all-symbols? '(a b (c (d e f)) (g 2 h))) $==>$ \#f
\end{lisp}

Assuming that the predicates {\tt symbol?, number?} and {\tt atom?}
are available, and return {\tt true} if the argument is of the
appropriate type, write the procedure {\tt all-symbols?}.

\emptybox{6.5in}{4in}

\newpage

{\bf Question 8 {\bf (15 points)}:}

The following two procedures give a very general method for operating
on trees that are represented as lists of lists:

\begin{lisp} 
(define (op-on-list op init list)
  (if (null? list)
      init
      (op (car list)
          (op-on-list op init (cdr list)))))
\null
(define (op-on-tree op init single tree)
  (define (opt x) (op-on-tree op init single x))
  (if (not (pair? tree))
      (single tree)
      (op-on-list op init (map opt tree))))
\end{lisp}

where {\tt pair?} is a predicate that returns {\tt true} if the
argument's value points to a cons cell.

Suppose we define 

\begin{lisp}
(define test '(1 (2 (3) 4)))
\end{lisp}


What is returned by evaluating each of the following
expressions?

\begin{lisp}
(op-on-tree *
            1
            (lambda (x) x)
            test)
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt

\begin{lisp}
(op-on-tree cons
            '()
            (lambda (x) (* 2 x))
            '(1 2 3))
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt

\begin{lisp}
(op-on-tree cons
            '()
            (lambda (x) (* 2 x))
            test)
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt

\begin{lisp}
(op-on-tree append
            '()
            (lambda (x) (list x))
            '(1 2 3))
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt

\begin{lisp}
(op-on-tree append
            '()
            (lambda (x) (list x))
            test)
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}


\end{document}


{\bf Part a:}  For each of the following expressions, indicate whether
or not evaluating them returns the number 9.  Assume that the
procedure {\tt square} is defined in the obvious manner.  The
definition of {\tt reduce} is:

\begin{lisp}
(define (reduce op init list)
  (if (null? list)
      init
      (op (car list)
          (reduce op init (cdr list)))))
\end{lisp}

\vskip 20pt

\begin{tabular}{lll}
Yes& No & Expression\\
\hline
&&\\
\emptybox{.25in}{.25in}& \emptybox{.25in}{.25in}&
\begin{lisp} 
((lambda (x) (x 3)) (lambda (x) (* x x)))\end{lisp}\\
&&\\
\emptybox{.25in}{.25in}& \emptybox{.25in}{.25in}&
\begin{lisp}
((lambda (y)
   ((lambda (x) (x y)) square))
 3)
\end{lisp}\\
&&\\
\emptybox{.25in}{.25in}& \emptybox{.25in}{.25in}&
\begin{lisp}
((lambda (x) (* x y)) 3 3)
\end{lisp}\\
&&\\
\emptybox{.25in}{.25in}& \emptybox{.25in}{.25in}&
\begin{lisp}
(reduce +
        0
        (map (lambda (x) (+ x 1))
             (list 3 4)))
\end{lisp}\\
&&\\
\emptybox{.25in}{.25in}& \emptybox{.25in}{.25in}&
\begin{lisp}
((lambda (x) (lambda (y) 9)) 9)
\end{lisp}\\
\end{tabular}

\vskip 20pt

{\bf Part b:} Choose the {\bf  best} answer for the following question:

In the Henderson picture language (described in lecture and on
problem set 3), the means of combination satisfy the notion of {\bf closure}.
An example of this is:

\begin{enumerate}


\item  Painters are represented as procedures.

\item  Painters can draw on non-rectangular frames.

\item Painters can be based on two-dimensional images as well as on line
drawings. 


\item The {\tt beside} of two painters is a painter.

\item {\tt Above} and {\tt beside} are defined as ordinary Scheme procedures.

\end{enumerate}


The best choice is  \emptybox{.25in}{.25in}.


\newpage

{\bf Part c:}

For each of the following statements, check the appropriate boxes to
indicate whether the statement is true for trade secret protection,
patent protection, or copyright protection.  Note that a statement may
be true for more than one kind of protection, or for none of them.

\begin{tabular}{cccl}
Trade&   Patent&  Copyright&\\
Secret&&&\\
\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\begin{minipage}[t]{4in}{
This is currently widely used to protect software in the US.}\end{minipage}\\
\\
\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\begin{minipage}[t]{4in}{This
form of protection lasts for 17 years.}\end{minipage}\\
\\
\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\begin{minipage}[t]{4in}{With
this form of protection, you are
liable for infringement even if you
had no knowledge of the product that
you are infringing.}\end{minipage}\\
\\
\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\emptybox{.25in}{.25in}&\begin{minipage}[t]{4in}{Lotus's
``look and feel'' suit against Borland alleges this kind of infringement.}\end{minipage}\\
\end{tabular}      

\vskip 20pt

{\bf Part d:}  Using the pattern matcher of Problem Set 4, we can attempt to
match the following patterns with the expression  {\tt (the black female
population)}.  In each case, indicate whether the pattern matches.  If
yes, what are the matches for the pattern variables?  If there is more
than one way to match, show all possibilities.  If no, what
is the cause of failure?  {\tt Sex-group} and {\tt race-group} are
defined as follows:

\begin{lisp}
(define (sex-group exp fail succeed)
  (if (memq exp '(male female))
      (succeed exp fail)
      (fail)))
\null
(define (race-group exp fail succeed)
  (if (memq exp '(white black asian amerind other))
      (succeed exp fail)
      (fail)))
\end{lisp}

\vskip 10pt

Expression 1: \begin{lisp}
(the (? x race-group) (? y sex-group) population)
\end{lisp}

\begin{tabular}{l|l}
Matches? & Variable matches or cause for failure\\
\hline
&\\
Yes &\\
&\\
No&\\
&\\
\end{tabular}

\newpage

Expression 2: \begin{lisp}
(the (? y sex-group) (? x race-group) population)
\end{lisp}

\begin{tabular}{l|l}
Matches? & Variable matches or cause for failure\\
\hline
&\\
Yes &\\
&\\
No&\\
&\\
\end{tabular}

\vskip 10pt

Expression 3: \begin{lisp}
(the (? x race-group) (? y) population)
\end{lisp}

\begin{tabular}{l|l}
Matches? & Variable matches or cause for failure\\
\hline
&\\
Yes &\\
&\\
No&\\
&\\
\end{tabular}

\vskip 10pt

Expression 4: \begin{lisp}
(the (?? x) population)
\end{lisp}

\begin{tabular}{l|l}
Matches? & Variable matches or cause for failure\\
\hline
&\\
Yes &\\
&\\
No&\\
&\\
\end{tabular}

\vskip 10pt

Expression 5: \begin{lisp}
(the (? x) population)
\end{lisp}

\begin{tabular}{l|l}
Matches? & Variable matches or cause for failure\\
\hline
&\\
Yes &\\
&\\
No&\\
&\\
\end{tabular}

\vskip 10pt

Expression 6: \begin{lisp}
(the (?? x) (?? y) population)
\end{lisp}

\begin{tabular}{l|l}
Matches? & Variable matches or cause for failure\\
\hline
&\\
Yes &\\
&\\
No&\\
&\\
\end{tabular}

\newpage

{\bf Question 2 {\bf (12 points)}:}

Show how to extend the basic differentiator to handle more kinds of
expressions.  In particular, implement the differentiation rule

\[ \frac {d(u^{n})}{dx}=nu^{n-1}\left( \frac{du}{dx}\right) \]

\noindent
by adding a new clause to the {\tt deriv} program (You do not need to
rewrite all of {\tt deriv}, you simply need to show the clause you
would add).
Also extend the interface to the data by defining
appropriate procedures {\tt exponentiation?}, {\tt base}, {\tt exponent},
and {\tt make-exponentiation}.  (You may use the symbol {\tt **} to denote
the exponentiation operator.)  

(Recall that this problem was assigned for tutorial for the week of
February 28.)


\begin{lisp}
(define (deriv exp var)
   (cond ...
         \emptybox{5in}{2in}
         ...))
\end{lisp}

\vskip 10pt

\emptybox{6.5in}{4in}

\newpage

{\bf Question 3 {\bf (38 points)}:}  

The following two procedures give a very general method for operating
on trees that are represented as lists of lists:

\begin{lisp}
(define (reduce op init list)
  (if (null? list)
      init
      (op (car list)
          (reduce op init (cdr list)))))
\null
(define (accumulate-tree op init single pred tree)
  (define (acc x) (accumulate-tree op init single pred x))
  (if (pair? tree)
      (reduce op init (map acc tree))
      (if (pred tree)
          (single tree)
          init)))
\end{lisp}

Suppose you are given the following test tree:

\begin{lisp}
(define test-tree
  '(1 (4 (3 2)) (8 7 (6 5))))
\end{lisp}

{\bf Part a:}  Draw the box and pointer diagram representing the
structure associated with {\tt test-tree}.

\vskip 20pt

\emptybox{6.5in}{4.5in}

\newpage

{\bf Part b:}  What is returned by evaluating each of the following
expressions?


\begin{lisp}
(accumulate-tree +
                 0
                 (lambda (x) x)
                 (lambda (x) true)
                 test-tree)
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt



\begin{lisp}
(accumulate-tree cons
                 '()
                 (lambda (x) x)
                 (lambda (x) true)
                 '(1 2 3))
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt

\begin{lisp}
(accumulate-tree cons
                 '()
                 (lambda (x) x)
                 (lambda (x) true)
                 test-tree)
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt

\begin{lisp}
(accumulate-tree append
                 '()
                 (lambda (x) (list x))
                 (lambda (x) true)
                 '(1 2 3))
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}

\vskip 10pt

\begin{lisp}
(accumulate-tree append
                 '()
                 (lambda (x) (list x))
                 (lambda (x) true)
                 test-tree)
\end{lisp}

\vskip 10pt

Result: \emptybox{5.5in}{.35in}


\newpage 

{\bf Part c:}

In each of the cases below, complete the expression so that it will
return the specified result.  Assume in each case that all of the
leaves of the tree are integers.

The product of all the leaves of the tree that are greater than 6:

\begin{lisp}
(accumulate-tree \emptybox{4in}{.5in}
                 \emptybox{4in}{.5in}
                 \emptybox{4in}{.5in}
                 \emptybox{4in}{.5in}
                 test-tree)
\end{lisp}

\vskip 10pt

The sum of the squares of all the odd leaves of the tree (assume that
the predicate {\tt odd?} is available):

\begin{lisp}
(accumulate-tree \emptybox{4in}{.5in}
                 \emptybox{4in}{.5in}
                 \emptybox{4in}{.5in}
                 \emptybox{4in}{.5in}
                 test-tree)
\end{lisp}

\newpage 


{\bf Part d:}
Suppose that we change the definition of {\tt reduce} as follows:

\begin{lisp}
(define (reduce op init list)
  (define (iter elements value)
    (if (null? elements)
        value
        (iter (cdr elements)
              (op value (car elements)))))
  (iter list init))
\end{lisp}

\noindent and that we use this new version of {\tt reduce} in {\tt accumulate-tree}.

For each of the following expressions, indicate whether we get the  same
result regardless of which version of {\tt reduce} we use.

\begin{lisp}
(accumulate-tree +
                 0
                 (lambda (x) x)
                 (lambda (x) true)
                 test-tree)
\end{lisp}

\begin{tabular}{cc}
Same Result?:&\emptybox{.5in}{.25in}\\
\end{tabular}

\vskip 10pt


\begin{lisp}
(accumulate-tree cons
                 '()
                 (lambda (x) x)
                 (lambda (x) true)
                 test-tree)
\end{lisp}


\begin{tabular}{cc}
Same Result?:&\emptybox{.5in}{.25in}\\
\end{tabular}

In general, what property must the argument {\tt op} satisfy so that
evaluating the expression

\begin{lisp}
(accumulate-tree op init single pred tree)
\end{lisp}

will give the same result using either version  of {\tt reduce}?

\vskip20pt

\emptybox{6.5in}{2.75in}


\newpage

{\bf Question 4 {\bf (26 points)}:}    In problem set 2, you built a
system to play Black Jack, in which you used a simple data
structure to represent hands of cards without worrying about the
details of its implemention.  In that abstraction, a hand consisted of
an {\it up card} and a {\it card set}.  The operations on card sets
were {\tt card-set-create}, {\tt card-set-add} and {\tt card-set-total}.
Individual cards were represented as numbers from 1 to 10.  

If we represent card sets as lists of cards, as in the problem set,
then our card set operations are implemented as

\begin{lisp}
(define (card-set-create first-card)
  (list first-card))
\null
(define (card-set-add set card)
  (cons card set))
\null
(define (card-set-total set)
  (reduce + 0 set))
\end{lisp}


\vskip 10pt

{\bf Part a:}  Implement a procedure called {\tt card-set-how-many},
which takes as input a card set, and a card, and returns the number of
such cards in the card set.  For example, if a card set has three 8's
in it, then {\tt card-set-how-many} should return 3. If there are no
cards of the specified value in the set, the procedure should return
0.

Using the representation above, implement {\tt card-set-how-many}.

\emptybox{6.5in}{2in}


{\bf Part b:}  Now suppose we decide to represent a card set as a list
of cards in non-decreasing order, for example {\tt (1 3 3 4 6 6)}.


Show how to implement {\tt card-set-add} in this new representation.

\emptybox{6.5in}{2in}


{\bf Part c:}
This second representation gives you an opportunity to implement {\tt
card-set-how-many} in a more efficient way than in part a.  Write such
an implementation:

\emptybox{6.5in}{2in}


Does this change the order of growth in the time required by this operation?

\emptybox{.5in}{.25in}

{\bf Part d:}  A third way we can represent a card set is as a
procedure that takes a card as argument and returns the number of
cards of that type in the card set.  For this representation, {\tt
card-set-how-many} is simply implemented as:

\begin{lisp}
(define (card-set-how-many card card-set)
  (card-set card))
\end{lisp}

\noindent
and {\tt card-set-create} is implemented as

\begin{lisp}
(define (card-set-create first-card)
  (lambda (card)
     (if (= card first-card)
         1
         0)))
\end{lisp}


Implement {\tt card-set-add} for this representation.

\emptybox{6.5in}{2in}

\newpage

{\bf Part e:}  Complete the following implementation of {\tt
card-set-total} for the representation used in part d:

\begin{lisp}
(define (card-set-total card-set)
  (reduce +
          0
          (map (lambda (n)
                  \emptybox{4in}{.5in})
               '(1 2 3 4 5 6 7 8 9 10))))
\end{lisp}
    

\end{document}

As in the tutorial problem for
PS3, define a procedure {\tt butlast},
with the property that given a list of $n$ elements as input, it
returns as output a list of the first $n-1$ elements.  If the input is
the empty list, it should return the empty list.

For example, 

\begin{lisp}       
(butlast '(1 2 3 4 5))
;Value: (1 2 3 4)
\end{lisp}       

\vskip 20pt

\emptybox{6.5in}{3in}

Write an analogous procedure {\tt butfirst}, that given a list as
input returns as output a list excluding the first element.

\vskip 10pt

\emptybox{6.5in}{3in}

\newpage




Suppose that precincts is a list of precinct data structures
created in a fashion similar to {\tt  p1},
e.g.:

\begin{lisp}
(define precincts (list (make-precinct ...)
                        (make-precinct ...)
                        ...
                        (make-precinct ...)))
\end{lisp}

We want to return a sum of the number of votes for Clinton
from all the precincts.  Below are a series of expressions
to calculate this sum.  For each, indicate if it returns the
correct sum, and if not, very briefly explain why it is incorrect.

Assume the following are provided:

\begin{lisp}
(define (clinton? x)
  (eq? (candidate x) 'clinton))
\end{lisp}

\begin{enumerate}

\item 
\begin{lisp}
(accumulate + 0
            (map (lambda (z)
                   (tally (first-entry z)))
                 (map (lambda (x)
                        (filter clinton? x))
                      (map votes precincts))))
\end{lisp}

Correct? \emptybox{.5in}{.25in}

If not, why not?

\emptybox{6.5in}{1in}


\item 
\begin{lisp}
 (accumulate + 0 
             (map tally
                  (filter clinton? 
                          (map votes precincts))))
\end{lisp}

Correct? \emptybox{.5in}{.25in}

If not, why not?

\emptybox{6.5in}{1in}


\item 
\begin{lisp}
(accumulate + 0 
            (map tally
                 (filter clinton? 
                         (accumulate append '()
                                     (map votes precincts)))))
\end{lisp}

Correct? \emptybox{.5in}{.25in}

If not, why not?

\emptybox{6.5in}{1in}


%3) 
%
%
%\begin{lisp}
%(accumulate + 0
%            (map tally
%                 (map (lambda (x)
%                        (first-entry (filter (lambda (y) (eq? (candidate y) 'clinton))
%                                             (votes x))))
%                      precincts)))
%\end{lisp}
%
%Correct? \emptybox{.5in}{.25in}
%
%If not, why not?
%
%\emptybox{6.5in}{1in}
%


\item 
\begin{lisp}
(accumulate + 0
              (map tally
                    (map (lambda (x)
                            (filter clinton? x))
                         (map votes precincts))))
\end{lisp}

Correct? \emptybox{.5in}{.25in}

If not, why not?

\emptybox{6.5in}{1in}

\end{enumerate}
