\documentclass[twocolumn]{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

\title{6.001 Tutorial 4}
\author{David Ziegler}
\date{October 4, 2004}
\maketitle

\section{Quiz Stuff}
\begin{itemize}
\item Quiz, Thursday, 7:30 -- 9:30 pm
\item Room 32-123 (where we have lecture)
\item One page of notes
\item Review session tonight and tomorrow (LAs), 7 pm, 34-302
\item Office hours tomorrow (me), 3 -- 4 pm, here
\end{itemize}

\section{Project Comments}
\begin{itemize}
\item Please, please, please indent your code.
\item Please, please, please document your code.
\item Please, please, please test your code and include the results.
\end{itemize}

\section{Higher-Order Procedures}
Higher-order procedures are procedures that either accept procedures
as arguments or return procedures their value.

\begin{verbatim}
;; This procedure curries a function,
;; e.g. it takes a function of two
;; inputs and returns a function of
;; one input, that returns a function
;; of one input, that does the same
;; thing
;; ex: (+ 1 2) ==> 3
;; (((curry +) 1) 2) ==> 3
(define (curry f)



\end{verbatim}

\begin{verbatim}
;; This procedure composes two
;; functions f and g, each of one
;; argument, and returns a procedure
;; of one arg that does (f (g x))
(define (compose f g)


\end{verbatim}

\begin{verbatim}
;; This procedure applies f to each
;; element of the list, and returns a
;; new list made from those values
(define (map f lst)




\end{verbatim}

\begin{verbatim}
;; This procedure returns a new list
;; containing the elements in the
;; original for which pred is true
(define (filter pred lst)




\end{verbatim}

\begin{verbatim}
;; This procedure combines all the
;; elements of lst using the binary
;; operation op, terminating with init
(define (fold-right op init lst)




\end{verbatim}

\clearpage
\onecolumn
\section{Queues}
A queue is a data structure that stores elements in order.  Elements
are \verb+enqueue+d onto the tail of the queue.  Elements are
\verb+dequeue+d from the head of the queue.  Thus, the first element
enqueued is also the first element dequeued (FIFO,
first-in-first-out).  The \verb+head+ operation is used to get the
element at the head of the queue.

\begin{verbatim}
(head (enqueue 5 (empty-queue)))
;Value: 5

(define q (enqueue 4 (enqueue 5 (enqueue 6 (empty-queue)))))

(head q)
;Value: 6

(head (dequeue q))
;Value: 5
\end{verbatim}

Decide on an implementation for queues, then draw a box-and-pointer
represention of the value of \verb+q+ as defined above.
\vspace{1in}

\begin{verbatim}
;; This procedure returns an empty queue
(define (empty-queue)

\end{verbatim}
Time = $\Theta( \; \; \; \; \; )$, space = $\Theta( \; \; \;
\; \;)$, $n =$

\begin{verbatim}
;; This procedure returns a new queue with the element added to the tail
(define (enqueue x q)



\end{verbatim}
Can you do this with {\tt fold-right}? \\
Time = $\Theta( \; \; \; \; \; )$, space = $\Theta( \; \; \;
\; \;)$, $n =$

\begin{verbatim}
;; This procedure returns a new queue with the head removed
(define (dequeue q)



\end{verbatim}
Time = $\Theta( \; \; \; \; \; )$, space = $\Theta( \; \; \;
\; \;)$, $n =$

\begin{verbatim}
;; This procedure returns the value of the head of the queue
(define (head q)



\end{verbatim}
Time = $\Theta( \; \; \; \; \; )$, space = $\Theta( \; \; \;
\; \;)$, $n =$

\section{Practice With HOPs}
Suppose \verb+lst+ is bound to the list (1 2 3 4 5 6 7). Using
\verb+map+, \verb+filter+, and/or \verb+fold-right+, write an
expression involving \verb+lst+ that returns:

\begin{itemize}
\item \verb+(1 4 9 16 25 36 49)+
\begin{verbatim}

\end{verbatim}

\item \verb+(1 3 5 7)+
\begin{verbatim}

\end{verbatim}

\item \verb+((1 1) (2 2) (3 3) (4 4) (5 5) (6 6) (7 7))+
\begin{verbatim}

\end{verbatim}

\item \verb+((2) ((4) ((6) #f)))+
\begin{verbatim}

\end{verbatim}

\item The maximum element of \verb+lst+: 7
\begin{verbatim}

\end{verbatim}

\item The last pair of \verb+lst+: (7)
\vspace{.3in}

\end{itemize}

\end{document}