% -*- Mode: Tex -*-

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

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

{\Large\bf 0. Announcements}

$\bullet$ Quiz 1 in 1 week!  Wednesday, March 11th, 1998.  5pm - 7pm
XOR 7pm - 9pm.

\vskip .1in

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

{\Large\bf 1. Student Presentation}

Write a procedure that finds the last pair in a list and returns
it. Use box-and-pointer diagrams to demonstrate that your procedure
works for all legal inputs.

\vskip .1in


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

{\Large\bf 2. All Pairs}

Write the function {\tt all-pairs} that takes a list and returns a
list of all pairs of the elements in the list.  For example, 
\beginlisp
(all-pairs '(1 2 3 4)) ==>  ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
\endlisp

\beginlisp
(define (all-pairs s)
  (if (null? s)
      nil
      (append (map (lambda (x) (list (car s) x)) (cdr s))
              (all-pairs (cdr s)))))
\endlisp

\vskip .1in

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

{\Large\bf 3. Depth of a Tree}

Write a function {\tt depth} that takes a tree and returns the maximum
depth of the tree.  Note that this is equivalent to the maximum number
of parenthesis open at any given time when scheme prints the tree.
For example, 
\beginlisp
(depth '((1 (2) ((4 5) 6)) 7 8)) ==> 4
\endlisp

\beginlisp
(define (depth tree)
  (cond ((pair? tree)
         (max
          (+ 1 (depth (car tree)))
          (depth (cdr tree))))
        (else 0)))
\endlisp

\vskip .1in

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

{\Large\bf 4. Representing Sets}

A set is a mathematical object defined as a collection of unique
objects (i.e.\ an element appears at most once in a set).  To model
sets, we need to build an implementation that supports several
operations.  Build an implementation for sets of symbols, using
unordered lists as the basic representation.  Try to use map, filter,
and accumulate where appropriate.

$\bullet$ {\tt element?} takes as input an element and a set and returns
true if and only if the element is in the set.

\beginlisp
(define (element? x s)
  (cond ((null? s) \#f)
        ((eq? x (car s)) \#t)
        (else (element? x (cdr s)))))
\endlisp

\newpage
$\bullet$ {\tt adjoin} takes as input an element and a set and returns a
new set with that element added.  Remember that an element can appear
at most once in a set.

\beginlisp
(define (adjoin x s)
  (if (element? x s)
      s
      (cons x s)))
\endlisp

$\bullet$ {\tt union} takes as input two sets and returns a new set
containing any element contained in either of the input sets.

\beginlisp
(define (union s t)
  (accumulate adjoin t s))
\endlisp

$\bullet$ {\tt intersection} takes as input two sets and returns a new
set containing any element contained in both of the input sets.  {\it
Here's a version of intersection that a student from class came up
with.  This is more elegant than the one I originally presented.}

\beginlisp
(define (intersection s t)
  (filter (lambda (x) (if (element? x t) x \#f))
          s))
\endlisp

$\bullet$ {\tt set-} takes as input two sets and returns a new set
containing all elements of the first set that are not in the second set

\beginlisp
(define (set- s t)
  (define (remove x s)
    (filter 
      (lambda (y) (if (eq? x y) \#f y))
      s))
  (accumulate remove s t))
\endlisp

What are the orders of growth of these functions in time and space?

\begin{tabular}{|l|c|c|}
\hline
& Time & Space \\
\hline
{\tt element?} & $\Theta(n)$ & $\Theta(1)$ \\ 
{\tt adjoin} & $\Theta(n)$ & $\Theta(1)$ \\ 
{\tt union} & $\Theta(n^2)$ & $\Theta(n)$ \\ 
{\tt intersection} & $\Theta(n^2)$ & $\Theta(n)$ \\ 
{\tt set-} & $\Theta(n^2)$ & $\Theta(n)$ \\
\hline
\end{tabular}

\vskip .1in

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

{\Large\bf 5. Ordered Sets}

Now build an implementation that uses ordered lists, i.e. in which the
elements appear in the data structure in increasing order.  For
symbols, the predicate {\tt symbol<} serves the same purpose as {\tt
<} does for numbers.  

$\bullet$ {\tt element?}

\beginlisp
(define (element? x s)
  (cond ((null? s) \#f)
        ((eq? x (car s)) \#t)
        ((symbol<? (car s) x)
         (element? x (cdr s)))
        (else \#f)))
\endlisp

\newpage
$\bullet$ {\tt adjoin}

\beginlisp
(define (adjoin x s)
  (cond ((null? s) (list x))
        ((symbol<? x (car s))
         (cons x s))
        ((eq? x (car s))
         s)
        (else
         (cons (car s)
               (adjoin x (cdr s))))))
\endlisp

$\bullet$ {\tt union}

\beginlisp
(define (union s t)
  (cond ((null? s) t)
        ((null? t) s)
        ((eq? (car s) (car t))
          (cons (car s) (union (cdr s) (cdr t))))
        ((symbol<? (car s) (car t))
          (cons (car s) (union (cdr s) t)))
        (else
          (cons (car t) (union s (cdr t))))))
\endlisp

$\bullet$ {\tt intersection}

\beginlisp
(define (intersection s t)
  (cond ((null? s) nil)
        ((null? t) nil)
        ((eq? (car s) (car t))
          (cons (car s) (intersection (cdr s) (cdr t))))
        ((symbol<? (car s) (car t))
          (intersection (cdr s) t))
        (else
          (intersection s (cdr t)))))
\endlisp

$\bullet$ {\tt set-}

\beginlisp
(define (set- s t)
  (cond ((null? s) nil)
        ((null? t) s)
        ((eq? (car s) (car t))
          (set- (cdr s) (cdr t)))
        ((symbol<? (car s) (car t))
          (cons (car s) (set- (cdr s) t)))
        (else
          (set- s (cdr t)))))
\endlisp

\vskip 0.1in

What are the orders of growth in time for each of these operations?

\begin{tabular}{|l|c|c|}
\hline
& Time & Space \\
\hline
{\tt element?} & $\Theta(n)$ & $\Theta(1)$ \\ 
{\tt adjoin} & $\Theta(n)$ & $\Theta(1)$ \\ 
{\tt union} & $\Theta(n)$ & $\Theta(n)$ \\ 
{\tt intersection} & $\Theta(n)$ & $\Theta(n)$ \\ 
{\tt set-} & $\Theta(n)$ & $\Theta(n)$ \\
\hline
\end{tabular}

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

\end{document}
