\documentstyle[12pt]{article}
\include{ianMacros}
%\newcommand\entryBlank[1]{\rule{#1}{0.1pt}\makeStrut{3.5ex}}
%\newcommand\stdBlank{\entryBlank{2.7in}}
\expandMargins{0.6in}

\begin{document}
% \pagestyle{empty}

\vspace*{0.5in}
\begin{centering}
{\huge
Comp 210 \\
Exam \#1 \\
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) List Templates
\begin{enumerate}
\item 
Write the data definition,
three examples,
and the template
for {\it List-of-Number}.
\vspace*{3in}

\item
Consider the function 
{\it insert: number, List-of-Number $\rightArrow$ List-of-Number}
which takes in a number and an {\em ordered} (non-decreasing) list of numbers,
and returns a list with the number inserted into the right place
in the list.
For example,
{\tt \mbox{(insert 8 (list 2 4 6 10))} = \mbox{(list 2 4 6 8 10)}}
(A.) Give three other examples, and (B.) write the function.
%(You needn't worry about duplicates.)
\vspace*{3.5in}

\pagebreak
\item
Consider the function 
{\it insert-sort: List-of-Number $\rightArrow$ List-of-Number},
which takes its unordered input, and returns the same elements
in a sorted (non-decreasing) list.
For example,
{\tt (insert-sort \mbox{(list 8 6 2 4 10)}) = \mbox{(list 2 4 6 8 10)}}
(A.) Give two other examples, and (B.) write the function.
(Be sure to follow the template!)
\vspace*{3.5in}
\end{enumerate}

\pagebreak

\item (25 pts)
An {\it Employee} is either a secretary 
(who has a name and salary), or a manager
(who has a salary, and a list of employees who they directly supervise).

\begin{enumerate}
\item
Write data definitions for {\it List-of-Employee},
and for {\it Employee}.
If these data definitions use any {\tt make-{\it someStruct}}s,
include appropriate {\tt define-struct}s.
\vspace*{3in}

\item
Give four 
%qualitatively 
different examples of {\it Employee}s.
\vspace*{1.4in}

\item
Write a template for 
{\it Employee},
and one for
{\it List-of-Employee}.

\vspace*{1.9in}

\vspace*{1.9in}

\item
Consider the function 
% {\it count-secretaries: employee $\rightArrow$ number}
{\it cost-to-company: employee $\rightArrow$ number},
which calculates the salary of that employee
and any employees {\em anywhere} under their supervision
(even indirectly).
Next to the sample employees you wrote above,
(A.) write in what {\it cost-to-company} returns on each of them.
(B.) Write the function.
\vspace*{3in}

\pagebreak
\end{enumerate}

\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 greater?: NatNum,NatNum $\rightArrow$ boolean},
which returns whether or not
its first argument is bigger than its second.
\vspace*{2.5in}
\end{enumerate}
\pagebreak

\item (20 pts)
The following code is the straightforward way
of calculating the sum of a list of numbers with and without
an accumulator.
\begin{verbatim}
;; sum: list-of-number --> number
;;
(define sum
  (lambda (data)
    (cond [(empty? data) 0]
          [(cons?  data) (+ (first data) (sum (rest data)))])))


;; sum-accum-helper: list-of-number, number --> number
;; Return the sum of sum-so-far and the numbers in data
;;
(define sum-accum-helper
  (lambda (sum-so-far data)
    (cond [(empty? data) sum-so-far]
          [(cons?  data) (sum-accum-helper (+ sum-so-far (first data))
                                           (rest data))])))

;; sum-accum: list-of-number --> number
;; Return the sum of the numbers in nums-to-add.
;;
(define sum-accum
  (lambda (nums-to-add)
    (sum-accum-helper 0 nums-to-add)))
\end{verbatim}
Hand evaluate the following expressions, showing 
the first two steps of the evaluation in complete detail, 
and then 
showing (only) the intermediate expressions
just before calling one of the above-defined functions.
Be careful not to drop/add parentheses.
(Of course, if you want to claim that two expressions have equal values,
use an equal-sign between them.)
To save a bit of writing, you may write {\tt sum-ah} as
shorthand for {\tt sum-accum-helper}.
\begin{itemize}
\item {\tt (sum (list 7 2.718 3.14))}
\vspace*{3in}
\item {\tt (sum-accum (list 7 2.718 3.14))}
\vspace*{3in}
\end{itemize}
Yes or no: Do {\it sum} and {\it sum-accum} always return
the same answer, for all possible inputs?
%Why or why not?

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