\batchmode










\documentstyle[11pt,psfig,epsf,landscape,twoside,color]{article}
\makeatletter

\pagestyle{myheadings}

%
\evensidemargin 35pt

%
\setcounter{secnumdepth}{0}

%

\setlength{\oddsidemargin}{0in}
%
\setlength{\textwidth}{6.5in}

%


\setlength{\topmargin}{-0.5in}
%
\setlength{\headheight}{0.25in}
%
\setlength{\headsep}{0.25in}
%
\setlength{\textheight}{8.5in}

%

\setlength{\parindent}{0in}

%
\setlength{\parskip}{\medskipamount}

%



%



%


%






%

\newlength{\hlessmm}
\setlength{\hlessmm}{\textwidth}
\addtolength{\hlessmm}{-2em}

\newlength{\hlessmmmm}
\setlength{\hlessmmmm}{\textwidth}
\addtolength{\hlessmmmm}{-4em}

%



%



%





%









\outer

\outer

\outer

{\obeyspaces\gdef {\ }}

%



 

%
\newlength{\illuswidth}
\setlength{\illuswidth}{\textwidth}
\addtolength{\illuswidth}{-7pt}

%


%



%


%



%


%








%














\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{-0.2in}

\definecolor{HiddenAnswer}{rgb}{1,1,1}
\definecolor{HighlitedAnswer}{rgb}{1,0,0}
\definecolor{EndOfAnswer}{rgb}{0,0,0}

\ifx\undefined\AnswerSheet

\else

\fi

%




\def\AnswerSheet{1}

\newcommand {\evalsto}{$\Longrightarrow$}

\newcommand {\hstrut}[1]{\hspace*{#1}}

\newcommand {\vstrut}[2]{\rule[#1]{0in}{#2}}

\newcommand {\hm}{\hspace*{1em}}

\newcommand {\hmm}{\hspace*{2em}}

\newcommand {\hmmm}{\hspace*{3em}}

\newcommand {\hmmmm}{\hspace*{4em}}

\newenvironment {tightlist}%
{\begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
}
}%
{\end{list}
}

\newcommand {\cf}{\footnotesize\tt}

\newcommand {\IP}{$\bullet$}

\newcommand {\RA}{{\Large \bf $\Rightarrow$}}

\newcommand {\goesto}{$\longrightarrow$}

\def\lisp#1{\footnotesize\tt #1}

\def\beginlispA{%
  \begin{minipage}[t]{\linewidth}
  \begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{0in}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \obeyspaces
  \obeylines \footnotesize\tt}

\def\beginlisp{%
  \begin{minipage}[t]{\linewidth}
  \begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \obeyspaces
  \obeylines \footnotesize\tt}

\def\endlisp{%
  \end{list}
  \end{minipage}
  }

\def\psfileprefix{/usr/nikhil/parle/}

\def\illustration#1#2{
\vbox to #2{\vfill\special{psfile=\psfileprefix#1.ps hoffset=-72 voffset=-45}}}

\newcommand {\closure}[2]{%
\begin{tabular}[t]{l}
\raisebox{-1.5ex}{%
  \setlength{\unitlength}{0.2ex}
  \begin{picture}(25,15)(0,-7)
   \put( 5,5){\circle{10}}
   \put( 5,5){\circle*{1}}
   \put( 5,5){\vector(0,-1){10}}
   \put(15,5){\circle{10}}
   \put(15,5){\circle*{1}}
   \put(15,5){\vector(1,0){12}}
  \end{picture}}
  \fbox{\footnotesize #2} \\ 
%
\hspace*{0.8ex} \fbox{\footnotesize #1}
\end{tabular}
}

\newcommand {\proc}[2]{%
\begin{tabular}{l}
params: #1 \\ 
body: #2 \\ 
\end{tabular}
}

\newcommand {\psetheader}[2]{%
\markboth{6.001, #1---#2}{6.001, #1---#2}
\begin{center}
MASSACHVSETTS INSTITVTE OF TECHNOLOGY \\ 
Department of Electrical Engineering and Computer Science \\ 
6.001---Structure and Interpretation of Computer Programs \\ 
#1 \\ 
\medskip
{\bf #2}
\end{center}
}

\newcommand {\problem}[1]{{\bf #1}}

\newcommand {\key}[1]{\fbox{{\sc #1}}}

\newcommand {\ctrl}{\key{ctrl}--}

\newcommand {\shift}{\key{shift}--}

\newcommand {\run}{\key{run} \ }

\newcommand {\runkey}[1]{\run \key{#1}}

\newcommand {\extend}{\key{extend} \ }

\newcommand {\kkey}[1]{\key{k$_{#1}$}}

\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}}

\def\itemx{\vspace{-0.1in}\item}

\def\ANSWER#1{{\color{HiddenAnswer} #1 \color{EndOfAnswer}}}

\def\ANSWER#1{{\color{HighlitedAnswer} #1 \color{EndOfAnswer}}}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
\setcounter{secnumdepth}{0}
{\newpage
\clearpage
\samepage \begin{tabular}{p{3.2in}|p{3.2in}}
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(if 0 1 2) {\Large \bf $\Rightarrow$}  {\color{HighlitedAnswer} 1 \color{EndOfAnswer}}
\null
(define (my-if pred conseq alt)
  (if (zero? pred) alt conseq))
\null
(my-if 0 1 2) {\Large \bf $\Rightarrow$}  {\color{HighlitedAnswer} 2 \color{EndOfAnswer}}
\null
(define (factorial n)
  (my-if n
         (* n (factorial (- n 1)))
         1))
\null
(fact 5) {\Large \bf $\Rightarrow$}  {\color{HighlitedAnswer} [infinite loop!] \color{EndOfAnswer}}

\end{list}
\end{minipage} 
} & {

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define x 5)
(define y 6)
(let ((x 7) 
      (y x))
  (+ x y))  {\Large \bf $\Rightarrow$}  {\color{HighlitedAnswer} 12 \color{EndOfAnswer}}
\null
((lambda (x y) ((y 6) x)) 4 
  (lambda (w) (lambda (z) (* 2 z))))  {\Large \bf $\Rightarrow$}  {\color{HighlitedAnswer} 8 \color{EndOfAnswer}}
\null
(list 1 (list 2 list 3) 4)  
  {\Large \bf $\Rightarrow$}  {\color{HighlitedAnswer} (1 (2 \#[procedure] 3) 4) \color{EndOfAnswer}}
\null
((if + - *) 4 3)  {\Large \bf $\Rightarrow$}  {\color{HighlitedAnswer} 1 \color{EndOfAnswer}}

\end{list}
\end{minipage} 
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \begin{tabular}{p{3.2in}|p{3.2in}}
{
The procedure {\tt count-pairs} that counts the number 
of {\tt cons} pairs in a tree structure. 

{\footnotesize\tt (count-pairs (list 2 (list 3 4) (list 5))) {\Large \bf $\Rightarrow$}  6}


\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
\null
(define (count-pairs tree)
{\color{HighlitedAnswer} 
  (if (pair? tree)
      (+ 1 (count-pairs (car tree))
           (count-pairs (cdr tree)))
      0) \color{EndOfAnswer}}
)

\end{list}
\end{minipage} 
} & {
The procedure {\tt copy-some} that copies the first {\tt n} elements
of a list 

{\footnotesize\tt (copy-some 3 (list 1 2 3 4 5)) {\Large \bf $\Rightarrow$}  (1 2 3)}


\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
\null
(define (copy-some n lst)
{\color{HighlitedAnswer} 
   (if (= n 0)
       nil
       (cons (car lst) 
             (copy-some (- n 1) (cdr lst))))
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Theta({\color{HighlitedAnswer} n \color{EndOfAnswer}})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline739: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Theta({\color{HighlitedAnswer} n^2 \color{EndOfAnswer}})$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline741: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline743: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\bullet$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline745: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Theta(1)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline747: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{tabular}{p{3.2in}p{3.2in}}
{
How can we do this?  Let's define a sequence as show to the right.
The list (1 3 5) would be represented as a list of pairs.  The {\tt
car}s are the elements of the list, and the {\tt cdr}s are the lengths
of the lists.  Fill in the blanks below to complete the abstraction.
} & {
\vspace{-0.4in}
\centerline{\psfig{figure=r09-1.ps,height=1in}}
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \begin{tabular}{p{3.2in}|p{3.2in}}
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define empty-seq nil)
(define seq-empty? null?)
\null
(define (head seq) {\color{HighlitedAnswer} (caar seq)            \color{EndOfAnswer}})
(define (tail seq) {\color{HighlitedAnswer} (cdr seq)             \color{EndOfAnswer}})
\null
(define (seq-length seq)
  (if (seq-empty? seq)
      0
      {\color{HighlitedAnswer} (cdar seq)                \color{EndOfAnswer}}))
\null
(define (attach x seq) 
{\color{HighlitedAnswer}   (cons (cons x (+ 1 (seq-length seq))) seq)
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 
} & {

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define (list->seq lst)
{\color{HighlitedAnswer} 
  (define (helper lst n)
    (if (null? lst) 
        nil
        (cons (cons (car lst) n)
              (helper (cdr lst) (- n 1)))))
  (helper lst (length lst))
 \color{EndOfAnswer}})
\null
(define (seq->list seq)
{\color{HighlitedAnswer} 
  (map car seq)
 \color{EndOfAnswer}})

\end{list}
\end{minipage} 
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \begin{tabular}{p{3.2in}p{3.2in}}
{
How about another way?  Here a sequence is a pair of two things.  The
{\tt car} is the original list, and the {\tt cdr} stores the lengths
of the list.  Fill in the blanks below to complete the abstraction.
} & {
\vspace{-0.4in}
\centerline{\psfig{figure=r09-2.ps,height=1.1in}}
}
\end{tabular}
}

{\newpage
\clearpage
\samepage \begin{tabular}{p{3.5in}|p{3.2in}}
{

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
(define empty-seq (cons nil nil))
(define (seq-empty? seq) (null? (car seq)))
\null
(define (head seq) {\color{HighlitedAnswer} (caar seq)                   \color{EndOfAnswer}})
(define (tail seq) {\color{HighlitedAnswer} (cons (cdar seq) (cddr seq)) \color{EndOfAnswer}})
\null
(define (seq-length seq)
  (if (seq-empty? seq)
      0 
      {\color{HighlitedAnswer} (cadr seq)                             \color{EndOfAnswer}}))
\null
(define (attach x seq)
{\color{HighlitedAnswer} 
  (cons (cons x (car seq)) 
        (cons (+ 1 (seq-length seq)) (cdr seq)))
 \color{EndOfAnswer}})

\end{list}
\end{minipage}  
} & {

\begin{minipage}[t]{\linewidth}
\begin{list}{$\bullet$}{%
\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{1.5em}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
}\item[]
\obeyspaces
\obeylines \footnotesize\tt 
\null
\null
(define (list->seq lst)
{\color{HighlitedAnswer} 
  (define (helper n)
    (if (= n 0)
        nil
        (cons n (helper (- n 1)))))
  (cons lst (helper (length lst)))
 \color{EndOfAnswer}})
\null
(define (seq->list seq) 
{\color{HighlitedAnswer} 
  (car seq)
 \color{EndOfAnswer}})

\end{list}
\end{minipage}       
} 
\end{tabular}
}

\stepcounter{section}

\end{document}
