\documentclass[boldsans]{article}
\usepackage{ccfonts,fullpage,graphics,rotating}
\usepackage{hyperref}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\title{CSC148, Lab \#2\\
  week of September 23rd, 2013}
\author{~}
\renewcommand{\today}{~}
\begin{document}
\maketitle

\noindent
To earn your lab mark you must seriously participate in the lab.  You
are graded on \textit{participation}, not results.  Please note that
participation includes showing up on time (10 minutes after the hour,
at U~ of~T).

\section*{General rules}

Same general
\href{http://www.cdf.toronto.edu/~heap/148/F13/Labs/lab01/handout.pdf}{rules}
as Lab \#1, in particular navigator and drivers.  You are encouraged to begin work on this lab once you arrive, and not
earlier.  If you do happen to finish some of it earlier, bring
no notes or electronic files, so that you can participate with a fresh
perspective during the lab.  Lab materials are found at \url{http://www.cdf.toronto.edu/~heap/148/F13/Labs/lab02/}

Show your work to your TA frequently, and feel free to them ask
questions  --- that's why they're here!  Don't hesitate to also ask
other students if you get stuck, and please be generous in helping
others.

\section*{Using stacks}
\label{usingstacks}

\subsection*{Getting started}

(Student \texttt{s1} drives and \texttt{s2} navigates.)

\begin{enumerate}
\item Save the file
  \href{http://www.cdf.toronto.edu/~heap/148/F13/Labs/lab02/stack.py}{stack.py},
  available at
  \begin{quotation}
    \url{http://www.cdf.toronto.edu/~heap/148/F13/Labs/lab02/}
  \end{quotation}
  \item Start \texttt{wing} and open \texttt{stack.py}
  \item Create a new file called \texttt{driver.py}, and add code to it so that
    it:
    \begin{enumerate}
    \item[(a)] creates a new Stack;
    \item[(b)] puts the string 'Hello' in the stack;
    \item[(c)] removes the string from the stack and prints it.   
    \end{enumerate}        
    All of the above should be under the  \verb+if __name__ == '__main__':+
    statement. 
\end{enumerate}

\subsection*{Using a stack}

(Switch roles: now, \texttt{s2} drives and \texttt{s1} navigates.)
\begin{enumerate}
\item Change \texttt{driver.py} to read in a list of lines from standard input,
  until the string "end" is typed, and put each line into a
  Stack. Remember that a ``read and process loop'' looks like this:
\begin{verbatim}
        Read a line
        while not done:
            Process the line that was read
            Read the next line
\end{verbatim}
You can read a line using: \texttt{input("Type a string:")}.

\item Add code at the end of driver.py to remove and print the lines
  you stored in the stack. When the stack becomes empty, end the
  program.
\end{enumerate}
Show your work to your TA before moving on to the next section. 

\section*{Queues}

A queue is another ADT that stores a sequence of items. Unlike a
stack, items are added at the ``back'' and removed from the ``front,''
in first-in, first-out order (like a lineup at a grocery store). Here
are the operations supported by the queue ADT:

\begin{itemize}
\item \texttt{enqueue(item)}: Add item to the back of the queue.
\item \texttt{dequeue()}: Remove and return the front item. Raise \texttt{EmptyQueueError}
    if the queue is empty.
\item \texttt{front()}: Return the front item without removing
  it. Raise \texttt{EmptyQueueError} if the queue is empty.
\item \verb+is_empty()+: Return True iff the queue is empty. 
\end{itemize}

\subsection*{Implementation}

(Switch roles again: \texttt{s1} drives and \texttt{s2} navigates.)

\begin{enumerate}
\item Write a \texttt{Queue} class in a file named \verb+queue.py+ to implement the
    queue ADT.
  \item Download the file
    \href{http://www.cdf.toronto.edu/~heap/148/F13/Labs/lab02/testqueue.py}{testqueue.py},
    open it in Wing, and run it to test your \texttt{Queue} class.
\end{enumerate}

\subsection*{Using a queue}

(Switch roles again: \texttt{s2} drives and \texttt{s1} navigates.)

\begin{quotation}
  \textbf{NEWS FLASH:} python has recently added a built-in module
  called \texttt{queue}, which in some environments (e.g. Wing) is
  seen before the \texttt{queue} module in your directory.  Here are
  two possible work-arounds:
  \begin{itemize}
  \item You could re-name the file \texttt{queue.py} to something unlikely to be a
    built-in python module (perhaps \verb+my_queue.py+, and also
    re-name your import statements in \texttt{testqueue.py,
      timequeue.py, driver.py} to match.
  \item You could look at the two lines in \texttt{testqueue.py} that
    occur before any import statements (the first of the two lines
    says \texttt{"import sys"}, and use that to make sure the the
    current directory is examined first.
  \end{itemize}
\end{quotation}

\begin{enumerate}
\item Modify \texttt{driver.py} so that it uses a queue instead of a stack, and
  expects input lines to contain integers (except for the "end"
  line).
  \begin{itemize}
  \item Recall that you can convert an input line to an integer by
    calling the int constructor.
  \item Store all the integers in a queue.
  \end{itemize}
\item Now make your program print the product of all the numbers that
    were in the queue. (Do this by removing the items in the queue one
    by one.)
\end{enumerate}
Show your work to your TA before moving on to the next section. 

\section*{Efficiency}

(Switch roles once more, with feeling: \texttt{s1} drives and \texttt{s2} navigates.)
\begin{enumerate}
\item Download the file \href{http://www.cdf.toronto.edu/~heap/148/F13/Labs/lab02/timestack.py}{timestack.py},
  open it in Wing, and run it to get information about the efficiency
  of the Stack class.

  How does the running time grow as a function of the number of
  items on the stack?

\item Download the file
  \href{http://www.cdf.toronto.edu/~heap/148/F13/Labs/lab02/timequeue.py}{timequeue.py},
  open it in Wing, and run it to get information about the efficiency of
  your Queue class.

  How does the running time grow as a function of the number of
  items in the queue?

\item  Get out a piece of paper and spend some time with your partner
  trying to figure out why your \texttt{Queue} class behaves this way. Also
  brainstorm possible solutions to this O(n) efficiency (where n is
  the number of items that are in the queue).

  Hint: Draw a list, and think about keeping track of ``front'' and
  ``back'' indices, and ignoring some parts of your list. Don't
  worry if you can't come up with a solution, but do spend some time
  discussing! 
\end{enumerate}
\end{document}
