% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Wednesday, February 10}

{\Large\bf 1. More Special Forms }

The special form {\bf begin} has the following form.  It evaluates
each one of the expressions in turn.  The value of the begin
expression is the value of the last expression.

\beginlisp
(begin <expr1> <expr2> ... <exprN>)
\endlisp

Example: 
\beginlisp
(begin (+ 5 3) (- x 5) (* 9 9))
\endlisp
Wait a second...  Why do we need this?

\vspace{0.1in}

The special form {\bf cond} has the following form.  Conditional
expressions are evaluated as follows. {\tt <pred1>} is evaluated, and
if that value is not {\tt \#f}, then the value of the cond clause is
the value of {\tt <expr1>}.  If {\tt <pred1>} evaluates to {\tt \#f},
then {\tt <pred2>} is evaluated, etc..  If all of the predicates are
{\tt \#f}, then the else expression {\tt <exprE>} is evaluated and
returned.

\begin{tabular}{p{3in}p{3in}}
{
\beginlisp
(cond (<pred1> <expr1>)
      (<pred2> <expr2>)
             ...
      (<predN> <exprN>)
      (else    <exprE>))
\endlisp
} &
{
\beginlisp
Example:  (define (sign x) 
            (cond ((> x 0) 1)
                   (< x 0) -1) 
                   (else 0))
\endlisp
}
\end{tabular}

\vspace{0.1in}
{\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 n m)
  (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)
\ANSWER{
  (define (mul4-iter m count ans)
    (cond ((= count 0) ans)
          ((even? count) 
           (mul4-iter (double m) (halve count) ans))
          (else
           (mul4-iter m (- count 1) (+ m ans)))))
  (mul4-iter m n 0)
}
)
\endlisp

\vspace{0.1in}

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

Consider the following two procedures.

\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
$\Rightarrow$ (count-down 11 3)
\ANSWER{ 11 8 5 2 }
\endlisp

\beginlisp
$\Rightarrow$ (count-up 11 3)
\ANSWER{ 2 5 8 11 }
\endlisp

\vspace{0.1in}

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)
\ANSWER{
   (define (iter val) 
     (cond ((> val x) \#t)
           (else (print val)
                 (iter (+ val by)))))
   (iter (modulo x by))
}
)
\endlisp

\vspace{0.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

{\Large\bf 5. Order of Growth 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$     

$\ANSWER{\theta(1) \;\;\;\;\;\; 1\cdot 1 \le 6 \le 6\cdot 1 \;\;\; 
\forall n > 0}$

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

$\ANSWER{\theta(n^2) \;\;\;\;\;\; 1\cdot n^2 \le n^2+3 \le 2\cdot n^2 \;\;\; 
\forall n > 2}$

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

$\ANSWER{\theta(n^3) \;\;\;\;\;\; 1\cdot n^3 \le 6n^3+3n^2+7n+100 \le 7\cdot n^3 \;\;\; 
\forall n > 100}$

(d) $R(n) = 5 \cdot \log(n^6)$

$\ANSWER{\theta(log(n)) \;\;\;\;\;\; 1\cdot \log(n) \le 5 \cdot \log(n^6) \le 40\cdot \log(n) \;\;\; 
\forall n > 1}$

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

$\ANSWER{\theta(8^n) \;\;\;\;\;\; 1\cdot 8^n \le 2^{3n+7} \le 2^8\cdot 8^n \;\;\; 
\forall n > 0}$

\vspace{0.1in}

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

\begin{tabular}{p{4in}p{2in}}
{
\beginlisp
(define (fact1 n)
  (if (= n 1)
       1
       (* n (factorial (- n 1)))))
\null
\null
\endlisp
} & 
{
Time = \ANSWER{$\theta(n)$} 

Space = \ANSWER{$\theta(n)$}
}
\\
{
\beginlisp
(define (fact2 n)
   (define (helper cur k)
       (if (= k 1)
           cur
           (helper (* cur k) (- k 1))))
   (helper 1 n))
\null
\null
\endlisp
} & 
{
Time = \ANSWER{$\theta(n)$} 

Space = \ANSWER{$\theta(1)$}
} \\
{
\beginlisp
(define (fib1 n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib1 (- n 1))
                  (fib1 (- n 2))))))
\null
\null
\endlisp
} &     
{
Time = \ANSWER{$\theta(2^n)$} 

Space = \ANSWER{$\theta(n)$}
} \\
{
\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))
\null
\null
\endlisp
} &
{
Time = \ANSWER{$\theta(n)$} 

Space = \ANSWER{$\theta(1)$}
}
\end{tabular}
\end{document}


