\documentstyle[12pt]{article}

%%%%%%%%% Part of ~ian/lib/ianMacros.tex, included for self-containment:
\newcommand \comment[1]    {}
\newcommand \makeStrut[1]  {\rule{0cm}{#1}}
\newcommand \entryBlank[1] {\rule{#1}{0.1pt}\makeStrut{3.5ex}}
\newcommand \stdBlank      {\entryBlank{2.7in}}

\newlength{\iansTempLength}

% \expandSideMargins: increase the side margins by the same amount:
% example: \expandSideMargins{.5in}
%
\newcommand{\expandSideMargins}[1]{
  \setlength{\iansTempLength}{#1}
  \addtolength{\textwidth}{2\iansTempLength}
  \addtolength{\oddsidemargin}{-\iansTempLength}
  \addtolength{\evensidemargin}{-\iansTempLength}
  }

% \expandTopBottomMargins: increase top/bottom margins by the same amount:
% example: \expandTopBottomMargins{.5in}
%
\newcommand{\expandTopBottomMargins}[1]{
  \setlength{\iansTempLength}{#1}
  \addtolength{\textheight}{2\iansTempLength}
  \addtolength{\topmargin}{-\iansTempLength}
  }

% \expandMargins: increase all four margins by the same amount:
% example: \expandMargins{.5in}
%
\newcommand{\expandMargins}[1]{
  \expandSideMargins{#1}
  \expandTopBottomMargins{#1}
  }
%%%%%%%% End excerpt of ~ian/lib/ianMacros.tex

\expandMargins{0.6in}

\begin{document}
% \pagestyle{empty}

\vspace*{-0.25in}
\begin{centering}
{\huge
Comp 210 \\
Midterm Exam \#1 \\
1998 Spring \\}
\end{centering}

\begin{centering}
{\small Due 98.Feb.23 (Mon), 10:00 in class or DH3102. \\}
\end{centering}

\vspace{0.75in}

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


This is a 
closed-book, closed-computer
{\bf two hour} take-home exam.
Read each problem carefully.
If you need to make any reasonable assumption, just state them in the margin.
Clarity and conciseness both contribute toward gettting full points.
Please refrain from discussing the exam until after the due-date.
You do not need to turn in any scratch-paper.
{\em All submitted sheets must be stapled!}


% You may only use the following built-in Scheme functions:
% {\em symbol? eq? boolean? null? cons first rest list
%  zero? positive? negative? add1 sub1 + - * / = < > <= >= }
% and the special forms {\em lambda define define-struct and or}.

% In your answers, you may presume you have a library of
% abstract data types we have discussed in class, including
% {\tt List}, {\tt OrderedList},
% {\tt Dictionary} (including
% binary search tree, balanced search tree, and hash table implementations),
% and {\tt PriorityQueue} 
% (including list, ordered-list, and heap implementations).
% When you need to use such an abstract data type, specify which 
% implementation
% you want only if it is important to the running-time for your problem.

\vspace{0.5in}

\noindent
Time started:\rule{1.0in}{0.1pt}\makeStrut{5.5ex} \\
Time finished:\rule{1.0in}{0.1pt}\makeStrut{5.5ex}

\vspace{4ex}

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

\vspace{2ex}

\noindent
{\bf Pledge:}
\vspace*{1.5in}


\pagebreak

\newcommand \dataize[1] {{\bf $<$}#1{\bf $>$}}
\newcommand \los {\dataize{List-of-Symbol}}
\newcommand \lolos {\dataize{List-of-List-of-Symbol}}
\newcommand \natNum {\dataize{NatNum}}


\begin{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%
\item (25 pts)

%\begin{enumerate}
Write the function {\it append2}, which takes
two \los s and returns the contents of the first followed by
the contents of the second.
Show the (recursive) calls to your function that occur in the
hand-evaluation of {\tt (append2 (list 'cyan 'teal) (list 'ochre))};
the answer should be
{\tt (list 'cyan 'teal 'ochre)}
(If two lines denote equal values, connect them with ``='';
don't write down a series of unrelated values.)
\\
Hint:
recur only on the first argument, 
never varying the second argument.

For this problem,
you don't need to write the data-definition and template for a \los,
% or a \lolos,
though if you are stuck these might help you, 
and they can provide partial credit.

You of course cannot appeal to the built-in function {\it append}.
\vspace*{2.5in}


%\item
%Write the function {\it append},
%which takes a \dataize{List-of-List-of-Symbols},
%and returns one list containing the contents of all the lists.
%For example
%\begin{verbatim}
%  (append (list 'four 'scores) (list 'and 'twenty 'tears) null (list 'ago))
%= (list 'four 'scores 'and 'twenty 'tears 'ago)
%\end{verbatim}
%\vspace*{2.5in}
%\end{enumerate}



\newpage
\item (25pts)
% Alternate possible choice: monus

Recall that a \natNum is
\begin{itemize}
\item 0, or
\item {\tt (add1 $m$)}, where $m$ is a \natNum.
\end{itemize}
\begin{enumerate}
\item 
Write the template for a function which handles
two arguments:
a \natNum\  {\em and} a \los.
Make sure all cases are covered.
\vspace*{2.5in}
\item
Write the function {\em nth-rest},
which takes 
a \natNum\ $n$
and 
a \los\  $los$,
and returns $los$ without its first $n$ items,
or the symbol {\tt 'list-too-short} if $los$ has fewer than $n$ items.
\begin{verbatim}
  (nth-rest 2 (list 'four 'scores 'and 'twenty))
= (list 'and 'twenty)
\end{verbatim}
You may simplify and combine cases if you like, but be careful!
Indicate whether or not you can rearrange your {\tt cond}'s
 question/answer pairs and still produce the correct answer.
\vspace*{2.5in}

\end{enumerate}


\newpage
\item (30pts)
\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}





\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.)









\end{enumerate}
\end{document}
