\documentstyle[12pt]{article}
\include{ianMacros}
%\newcommand\entryBlank[1]{\rule{#1}{0.1pt}\makeStrut{3.5ex}}
%\newcommand\stdBlank{\entryBlank{2.7in}}
\expandMargins{0.6in}
\newcommand \scheme[1] {{\it #1}}
\newcommand \dataize[1] {{\bf $<$}#1{\bf $>$}}

\begin{document}
% \pagestyle{empty}

\vspace*{0.5in}
\begin{centering}
{\huge
Comp 210 \\
Exam \#1 (alt)\\
1998 Fall \\}
\end{centering}

\vspace{0.75in}

\noindent
Name: \rule{2.7in}{0.1pt}\makeStrut{3.5ex}

\noindent
This is a closed-book, closed-computer, three hour exam.
%due 98.Oct.14 (Wed), 10:00. \\
This should be plenty enough time.
{\bf Make sure to read each problem carefully.}
If you need to make any reasonable assumption to do a problem,
  just state that in the margin. \\
Please refrain from discussing the exam until after the due-date.

Except as indicated,
 you may (only) use the following built-in Scheme functions:
 {\em symbol? eq? boolean? not empty? cons? cons first rest list
  number? zero? positive? negative? add1 sub1 + - * / = $<\  >\  \le\  \ge$}
 and the special forms {\em lambda define cond if define-struct and or}.

Include contracts for all functions you write.

\noindent
Time started:\rule{1.0in}{0.1pt}\makeStrut{3.5ex} \\
Time finished:\rule{1.0in}{0.1pt}\makeStrut{3.5ex} \\
{\bf Pledge:}
\vspace*{1.5in}

\begin{tabular}{|l|l|l|}
\hline
Problem 1 & 15 & \hspace*{0.75in} \\ \hline
Problem 2 & 20 & \\ \hline
Problem 3 & 25 & \\ \hline
Problem 4 & 20 & \\ \hline
Problem 5 & 20 & \\ \hline
Total     & 100 & \\ \hline
\end{tabular}



\pagebreak

\begin{enumerate}
\item (15 pts)
In the kingdom of Tuhundredtenia,
citizens 
whose income is less than \$210 are taxed 2\% of their income.
Those is income is more than that
are taxed 2\% of that first \$210,
 and 10\% of the rest of their income.
Consider the a function \mbox{{\tt tax: number $\rightArrow$ number}} which
given an income, computes the tax due.
(A.) Show three example input/outputs for {\tt tax},
and (B.) write the function.
Naturally,
changing any of the above the constants
should require changing only one number in your solution.
\vspace*{3in}


\pagebreak


\item (20 pts) Templates
In class, we constructed family trees for ancestors. For this
problem, we will construct family trees for descendants.
A descendant tree consists of the name of an individual and
trees for up to two children.
\begin{verbatim}
<dtree> := (nochild name) |
           (onechild name only) |
           (twochild name first second)
\end{verbatim}
where \verb|name| is a symbol and
\verb|only|, \verb|first|, and \verb|second| are dtrees.
\begin{enumerate}
\item
Give the \scheme{define-structure} statements that can be used to 
implement this data type in Scheme.  List the
constructors, predicates, and selectors created by these
define-structures.
\vspace{2in}
\item
Use your constructors to build an instance of
a descendant tree that consists of a person
named Joe who has a first born son Grant
and second born daughter named Beth.
(Neither Beth nor Grant have any children).
\vspace*{2in}
\item
Give the program template for a function \scheme{tree-proc}
that takes as input a descendant tree \scheme{t}.
\vspace*{2in}
\item
Based on the template, write the function
\scheme{any-only-children}, which takes a descendent tree
and returns whether or not anybody in the descendent tree
is an only child.
\vspace*{4in}

\end{enumerate}


\newpage
\item (25pts)
\begin{enumerate}
\newcommand \lod {\dataize{List-of-Doors}}
\newcommand \door {\dataize{Door}}
\item
Write a data description for a \lod\ (where \door s will be defined below).
\vspace*{1.6in}
\item
Write a template for a \lod-handling function,
assuming you will have a \door-handling function.
\vspace*{1.6in}
\item
There are three types of \door s, depending on what's
on the other side: 
Either a room (which has a name\comment{ and a size}, but nothing else),
or a hallway (which has \comment{size and }a name and a \lod),
or the outside (which has no further information).
Write a reasonable data description for a \door,
along with any accompanying {\tt define-struct}s.

\vspace{3.0in}

%\item Give two simple examples of \door s,
%an example of \lod, and then an example of a hallway.
%\vspace*{2.0in}
%
\newpage
\item Write a template for a \door-handling function;
remember to write in any appropriate recursive calls.
\vspace*{3.0in}

\item 
Write the function {\em can-escape?}, which
takes a \door\ and indicates whether it is possible to
reach the outside.
(Include the contract for each function you write.)
\vspace*{4in}

\end{enumerate}


\pagebreak

\item (20 pts)
Recall that a {\it NatNum} is either
\begin{itemize}
\item {\tt zero}, or
\item {\tt (add1 {\it NatNum})}.
\end{itemize}

\begin{enumerate}
\item
Write the template for a function which handles 
two {\it NatNum}s.\footnote{If your template
is written such that the {\em order} in which you list the cases
is essential to {\em covering} all cases,
make a comment to this effect.}
\vspace*{3in}


\item
An egalitarian computer virus, wanting to get rid of all 
inequality,\footnote{Presumably somebody who felt that
Tuhundredtenia's tax code didn't fairly account for cost-of-living.}
has destroyed all computer implementations 
of the functions $<, \le, \ge, >, -, abs$.
In fact, the only surviving numerical functions are 
$add1, sub1, zero?, positive?$.
Save the day by writing
{\it monus: NatNum,NatNum $\rightArrow$ NatNum},
which returns its first argument minus its second argument
(and returning 0 if its first argument is smaller than its second,
since there aren't any negative natural numbers).
\vspace*{2.5in}
\end{enumerate}
\pagebreak


\newpage
\item (20pts)
Write the function {\it max}, which takes a {\em non-empty} list of numbers,
and returns the largest number in the list.
{\bf Use an accumulator}, and do not use {\tt local}.
Show the (recursive) calls to your function(s)
that occur in
the hand-evaluation of {\tt (max (list 7 5 9 2))}.

Be sure to include a contract and description for all
functions you write.
(You don't need to write any data description for this problem,
though you are welcome to.)










\pagebreak
\end{enumerate}
\end{document}
