% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/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}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Friday, February 18}

{\Large\bf 1. Student Presentation}

Sometimes we have procedures that are supposed to be exact inverses of
each other.  For example, there might be a program that squares its
arguments and another that takes the square root. One test of these
programs is to see if the square root of the square of a number is the
original number.

Write, and explain to the class, a program named {\tt
make-inverse-test}. This program should take in two functions, some
procedure and its inverse, and it should return a function that, when
used, applies the procedure, applies the inverse, and returns the
result.

\vskip .15in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 2. Diophantine Equation Problem}

Given integers $a$ and $b$, we need to find integers $x$ and $y$ 
such that $ax + by = 1$.  
\vspace{-0.02in}

For this to be possible, $a$ and $b$ must not have any common factors 
(i.e. $\gcd(a,b)=1$). 

\def\mod{\mathop{\rm mod}}

By {\bf wishful thinking}, suppose we could solve this problem for a
different pair of integers, namely, the pair of integers $b$ and $r$,
where $r = a \mod b$.

\begin{itemize}
\vspace{-0.20in}
\item This means we would have found two integers $\overline{x}$ and
$\overline{y}$ such that $b \overline{x} + r \overline{y} = 1$
\vspace{-0.15in}
\item If $r = a \mod b$ then for some $q$, $a=bq+r$
\vspace{-0.13in}
\item We could then solve our original problem:
\vspace{-0.10in}
\begin{eqnarray} 
b \overline{x} + r \overline{y} = 1 \\
b \overline{x} + (a-bq) \overline{y} = 1 \\
a \overline{y} + b (\overline{x} - q\overline{y}) = 1 
\end{eqnarray}
\end{itemize}

\vspace{-0.07in}
Have we {\bf reduced} our problem, or just changed it?  Why?

\vspace{-0.07in}
Can we be sure that this process will always end eventually?  How?

\vspace{-0.07in}
Now, how would you write this in scheme?

\beginlisp
(define (solve-ax+by=1 a b)
  (if (= b 0)                           ; simple base case
      (if (= a 1)
          (list 1 0)                    ; X=1, Y is any integer
          (error "GCD wasn't 1"))
      (let ((q (quotient a b))
            (r (remainder a b)))
                                        ; find solution to simpler problem
        (let ((simpler (solve-ax+by=1 b r)))
          (let ((xbar (car simpler))    ; extract the pieces
                (ybar (cadr simpler)))
                                        ; construct and return solution
            (list ybar (- xbar (* ybar q))))))))
\endlisp

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 3. More Higher Order Procedures}

Consider the following two functions that we've seen before.  They
have a lot in common.

\begin{tabular}{p{3in}p{3in}}
\hbox{
\beginlisp
(define (mult m n)
  (if (= n 0)
      0
      (+ m (mul1 m (- n 1)))))
\endlisp
} & \hbox{
\beginlisp
(define (expt b e)
  (if (= e 0)
      1
      (* b (expt b (- e 1)))))
\endlisp
}
\end{tabular}

Can we generalize these functions using higher-order procedures?
Consider the generic accumulate function below.

\beginlisp
(define (accumulate combine test next ident)
  (define (recurse x y)
    (if (test y)
        ident
        (combine x (recurse x (next y)))))
  recurse)
\endlisp

How would you write {\tt mult} using {\tt accumulate}?

\beginlisp
(define mult (accumulate + zero? decr 0))
\endlisp

How would you write {\tt expt} using {\tt accumulate}?

\beginlisp
(define expt (accumulate * zero? decr 1))
\endlisp

How would you write {\tt repeated} using {\tt accumulate}?

\def\wordtimes{\mathop{\rm times}}
\vspace{-0.15in}
Recall that {\tt (repeated f n)} returns a function that takes a
value {\tt x} and returns $f^n(x)$ or $\overbrace{f(f(f(f...}^{n
\wordtimes}(x))))$, so {\tt ((repeated square 3) 2) == 256}

\beginlisp
(define repeated (accumulate compose zero? decr identity))
\endlisp

\vskip .05in

{\Large\bf 4. Iterative vs. Recursive}

Is the above {\tt accumulate} function {\bf iterative} or {\bf
recursive}?  How would you write a new {\tt accumulate2} function that
is the opposite?

\beginlisp
(define (accumulate2 combine test next ident)
  (lambda (x y) 
    (define (iter x y ans)
      (if (test y)
          ans
          (iter x (next y) (combine x ans))))
    (iter x y ident)))
\endlisp

\vskip .15in

What is the {\bf Order of Growth} of {\tt accumulate}?

\begin{tabular}{p{2in}p{2in}}
Time = $\Theta(1)$
&  
Space = $\Theta(1)$
\end{tabular}

\vskip .1in

What is the {\bf Order of Growth} of {\tt mult} defined by {\tt accumulate}?

\begin{tabular}{p{2in}p{2in}}
Time = $\Theta(n)$
&  
Space = $\Theta(n)$
\end{tabular}

\vskip .1in

What is the {\bf Order of Growth} of {\tt mult} defined by {\tt accumulate2}?

\begin{tabular}{p{2in}p{2in}}
Time = $\Theta(n)$
&  
Space = $\Theta(1)$
\end{tabular}

\vskip .1in

How would you need to change accumulate to allow for $\Theta(\log n)$
order of growth of {\tt mult}?


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
