% -*- 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}}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- February 11}

{\Large\bf 0. Announcements}

$\cdot$ Finally, a section staff! RI: Mike Leventon, {\tt
leventon@ai.mit.edu} \\
\hbox{\hspace{1.7in}}TA: George Dolina, {\tt gsdolina@mit.edu}

$\cdot$ Problem Set 1 is due this Friday {\bf in recitation}.  Late work
is not accepted.  Solutions will be posted on the web. 

$\cdot$ $\mu$Quiz this Friday.

$\cdot$ These notes will appear off of my home page, {\tt
http://www.ai.mit.edu/people/leventon/6001}

\vskip .25in
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 1. Student Presentation}

Write a procedure that computes {\tt a*b} by using only simple tests
like {\tt =} and the addition operator,\ {\tt\ +}. Explain what kind of
process your procedure causes (e.g. recursive versus iterative) and
why.

\vskip .25in

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

{\Large\bf 2. Iterative vs Recursive Processes}

Consider the following functions similar to those presented in lecture.

\beginlisp
(define (mul2 n m)
  (define (iter count ans)
    (if (= count 0)
        ans
        (iter (- count 1) (+ m ans))))
  (iter n 0))
\null
(define (mul3 m n)
  (cond ((= n 0) 0)
        ((even? n)
         (double (mul3 (halve n) m)))
        (else
         (+ m (mul3 (- n 1) m)))))
\endlisp

Now write a procedure mul4 that computes {\tt m*n} in $\theta(\log n)$
time in $\theta(1)$ space.

\beginlisp
(define (mul4 m n)
\endlisp
\vskip 1.4in
\beginlisp
)
\endlisp


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

{\Large\bf 3. More Iterative vs Recursive Processes}

\beginlisp
(define (count-down x by)
   (cond ((< x 0) \#t)
         (else (print x)
               (count-down (- x by) by))))
\null
(define (count-up x by)
   (cond ((< x 0) \#t)
         (else (count-up (- x by) by)
               (print x))))
\endlisp

What happens for each of

\beginlisp
$==>$ (count-down 11 3)
\endlisp

\vskip .2in

\beginlisp
$==>$ (count-up 11 3)
\endlisp

\vskip .2in

Write a function {\tt count-up-2} which performs the same way as {\tt
count-up}, but is an iterative process.

\beginlisp
(define (count-up-2 x by)
\endlisp
\vskip 1.0in
\beginlisp
)
\endlisp

\vskip .2in

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

{\Large\bf 4. Orders of Growth}

{\bf Why should we care?}

\begin{tabular}{|l|c|c|c|c|}
\hline
Name & $\theta$ notation & n = 2 & n = 10 & n = 100 \\
\hline
Constant & $\theta(1)$ & 1 & 1 & 1 \\
Logarithmic & $\theta(\log n)$ & 1 & 3.33 & 6.66 \\
Linear & $\theta(n)$ & 2 & 10 & 100 \\
Quadratic & $\theta(n^2)$ & 4 & 100 & 10,000 \\
Exponential & $\theta(2^n)$ & 4 & 1024 & $\approx 1.26 \times 10^{30}$\\
\hline
\end{tabular}

At 1 billion operations per second (current state of the art), if you
were to run an exponential time algorithm in the lab on a data set of
size $n=100$, you would be waiting for approximately $4 \times
10^{11}$ centuries for the code to finish running!

{\bf Formal Definition}

Let $R$ be some resource (e.g. space or time) used by a computation,
and suppose $R$ is a function of the size $n$ of a problem.  The
amount of resources consumed will be $R(n)$.  We say $R(n)$ has order
of growth $\Theta(f(n))$ written $R(n)= \Theta(f(n))$ if there is some constant
$k_1$ and $k_2$ independent of $n$ such that
\[k_1 f(n) \leq R(n) \leq k_2 f(n)\]
for sufficiently large $n$.

\newpage
{\bf Examples}

For the following functions $R$, find the simplest and slowest growing
function $f$ for which $R(n) = \Theta(f(n))$.

(a) $R(n) = 6$

(b) $R(n) = n^2 + 3$

(c) $R(n)  = 6n^3 + 3n^2 + 7n + 100$

(d) $R(n) = 2^{3n + 7}$

What are the Orders of Growth (space and time) for the two procedures
listed below?

\beginlisp
(define (fact1 n)
   (define (helper cur k)
       (if (= k 1)
           cur
           (helper (* cur k) (- k 1))))
   (helper 1 n))
\endlisp

\vskip 0.1in
Time = $\theta(\;\;\;\;)$
\vskip 0.1in
Space = $\theta(\;\;\;\;)$
\vskip 0.1in

\beginlisp
(define (fib1 n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib1 (- n 1))
                  (fib1 (- n 2))))))
\endlisp
    
\vskip 0.1in
Time = $\theta(\;\;\;\;)$
\vskip 0.1in
Space = $\theta(\;\;\;\;)$
\vskip 0.1in

\beginlisp
(define (fib2 n)
    (define (fib-iter a b count)
       (if (= count 0)
           b
           (fib-iter (+ a b) a (- count 1))))
 (fib-iter 1 0 n))
\endlisp

\vskip 0.1in
Time = $\theta(\;\;\;\;)$
\vskip 0.1in
Space = $\theta(\;\;\;\;)$
\vskip 0.1in

\end{document}
