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

\begin{verbatim}
(tax   0) = 0
(tax 100) = 2
(tax 210) = 4.2
(tax 310) = 4.2 + 10 = 14.2


(define THRESHOLD 210)     ; Place where income rates change;
(define POOR_RATE 0.02)
(define RICH_RATE 0.10)

;; tax: natNum, natNum --> number
;;
(define tax
  (lambda (income)
    (if (< income THRESHOLD)
        (* income POOR_RATE)
        (+ (* POOR_RATE THRESHOLD)
           (* RICH_RATE (- income THRESHOLD)))))
\end{verbatim}


%\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}
\begin{verbatim}
A List-of-Number is
  - empty
  - (cons <number> <List-of-Number>)

; Example data:
empty
(cons 3 empty)
(cons 8 (cons 3 (cons 2 empty)))

;; lon-fun: List-of-Number --> ?? [template]
;;
(define lon-fun
  (lambda (nums)
    (cond [(empty? nums) ...]
          [(cons?  nums) ...(first nums)...(lon-fun (rest nums))...])))
\end{verbatim}

\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}
\begin{verbatim}
;; insert: Number, List-of-Number --> List-of-Number
;;
(define insert
  (lambda (newNum nums)
    (cond [(empty? nums) (list newNum)]
          [(cons?  nums) (if (<= newNum (first nums))
                             (cons newNum nums)
                             (cons (first nums) (insert newNum (rest nums))])))
\end{verbatim}
%\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!)
\begin{verbatim}
;; insert-sort: List-of-Number --> List-of-Number
;;
(define insert-sort
  (lambda (nums)
    (cond [(empty? nums) empty]
          [(cons?  nums) (insert (first nums) (insert-sort (rest nums)))])))
\end{verbatim}
%\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}
\begin{verbatim}
A List-of-Employee is
  - empty
  - (cons <Employee> <List-of-Employee>)

An Employee is
  - (make-secretary <symbol> <number>)
  - (make-manager   <number> <List-of-Employee>)

(define-struct secretary (name salary))
(define-struct manager   (salary underlings))
\end{verbatim}

\item
Give four 
%qualitatively 
different examples of {\it Employee}s.
%\vspace*{1.4in}
\begin{verbatim}
(define sec1  (make-secretary 'georges 500))
(define sec2  (make-secretary 'claire  500))
(define sec3  (make-secretary 'bruno   700))
(define boss0 (make-manager 1000 empty))
(define boss1 (make-manager 2000 (list sec1 sec2)))
(define ceo   (make-manager 15000 (list boss0 bruno boss1)))
\end{verbatim}

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

%\vspace*{1.9in}
\begin{verbatim}
;; loe-fun: List-of-Employees --> ?? [template]
;;
(define loe-fun
  (lambda (employees)
     (cond [(empty? employees) ...]
           [(cons?  employees) ...(employee-fun (first employees))
                               ...(loe-fun (rest employees))])))
\end{verbatim}

%\vspace*{1.9in}
\begin{verbatim}
;; employee-fun: Employee  --> ?? [template]
;;
(define employee-fun
  (lambda (e)
     (cond [(manager? e)
            ...(manager-salary e)...(loe-fun manager-underlings e)]
           [(secretary? e)
            ...(secretary-name e)...(secretary-salary e)...])))
\end{verbatim}

\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}
\begin{verbatim}
(cost-to-company sec1)  =  500
(cost-to-company sec2)  =  500
(cost-to-company sec3)  =  700
(cost-to-company boss0) = 1000
(cost-to-company boss1) = 3000
(cost-to-company ceo)   =19700
\end{verbatim}
\begin{verbatim}
;; cost-of-loe: List-of-Employees --> number
;; Given a list of employees, calculate their total cost to the company.
(define cost-of-loe
  (lambda (employees)
     (cond [(empty? employees) 0]
           [(cons?  employees) (+ (cost-to-company (first employees))
                                  (cost-of-loe (rest employees))])))
\end{verbatim}

%\vspace*{1.9in}
\begin{verbatim}
;; cost-to-company: Employee  --> num
;;
(define cost-to-company
  (lambda (e)
     (cond [(manager? e)
            (+ (manager-salary e) (cost-of-loe manager-underlings e)]
           [(secretary? e)  (secretary-salary e)])))
\end{verbatim}




%\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}
\begin{verbatim}
;; twoNatNum-fun: NatNum, NatNum --> ?? [template]
;;
(define twoNatNum-fun
  (lambda (m n)
     (cond [(and (zero? m)     (zero? n)    )    ...]
           [(and (zero? m)     (positive? n)) ...(sub1 n)...]
           [(and (positive? m) (zero? n)    ) ...(sub1 m)...]
           [(and (positive? m) (positive? n)) 
            ...(twoNatNum-fun (sub1 m) (sub1 n))...])))
\end{verbatim}
This could be condensed as follows;
note that it requires closer inspection to make sure it covers
all cases.
\begin{verbatim}
;; twoNatNum-fun: NatNum, NatNum --> ?? [template]
;;  Abbreviated form: the order of the cases is essential for correctness.
;;
(define twoNatNum-fun
  (lambda (m n)
     (cond [(and (zero? m) (zero? n))                  ...]
           [(zero? m)                       ...(sub1 n)...]
           [(zero? n)                       ...(sub1 m)...]
           [else   ...(twoNatNum-fun (sub1 m) (sub1 n))...])))
\end{verbatim}



\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}
\begin{verbatim}
;; greater?: NatNum, NatNum --> boolean
;; Return (> m n).
;;
(define greater?
  (lambda (m n)
     (cond [(and (zero? m)     (zero? n)    ) #f]
           [(and (zero? m)     (positive? n)) #f]
           [(and (positive? m) (zero? n)    ) #t]
           [(and (positive? m) (positive? n)) 
            (greater? (sub1 m) (sub1 n))])))
\end{verbatim}
\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))}
\begin{verbatim}
  (sum (list 7 2.718 3.14))
= ((lambda (data)
     (cond [(empty? data) 0] 
           [(cons? data) (+ (first data)
                            (sum (rest data)))]))) 
   (list 7 2.718 3.14))
= (cond [(empty? (list 7 2.718 3.14)) 0]
        [(cons? (list 7 2.718 3.14)) (+ (first (list 7 2.718 3.14)) 
                                        (sum (rest (list 7 2.718 3.14))))])
  [Or, you could've eval'd primitives first,empty?,\&c. to go directly to]
= (cond [#f 0]
        [#t (+ 7 (sum (list 2.718 3.14)))])
= (+ 7 (sum (list 2.718 3.14)))
= (+ 7 (+ 2.718 (sum (list 3.14))))
= (+ 7 (+ 2.718 (+ 3.14 (sum empty))))
= (+ 7 (+ 2.718 (+ 3.14 0)))     [optional]
= (+ 7 (+ 2.718 3.14))           [optional]
= (+ 7 5.858)                    [optional]
= 12.858
\end{verbatim}
%\vspace*{3in}
\item {\tt (sum-accum (list 7 2.718 3.14))}
\begin{verbatim}
  (sum-accum (list 7 2.718 3.14))
= ((lambda (nums-to-add) (sum-accum-helper 0 nums-to-add))
   (list 7 2.718 3.14))
= (sum-accum-helper 0 (list 7 2.718 3.14))
= (sum-accum-helper 7 (list 2.718 3.14))
= (sum-accum-helper 9.718 (list 3.14))
= (sum-accum-helper 12.858 empty)
= 12.858
\end{verbatim}
%\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?

{\tt No.}
(As seen in lab, floating-point representation entails
innaccuracies, and adding the same
floating-point numbers in a different order may sometimes
yield a different result.
%\pagebreak
\end{enumerate}
\end{document}
