\documentclass[boldsans]{article}
\usepackage{ccfonts,fullpage,graphics,rotating}
\usepackage{hyperref}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\title{CSC148, Lab \#2\\
  week of January 20th, 2014}
\author{~}
\renewcommand{\today}{~}
\newcommand{\uline}{$\underline{~}$}
\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/W14/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/W14/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/W14/Labs/lab02/stack.py}{stack.py},
  available at
  \begin{quotation}
    \url{http://www.cdf.toronto.edu/~heap/148/W14/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 indented under the  \verb+if __name__ == '__main__':+
    statement.   You may well need an \textbf{import} statement to get started.
\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:")}.  Remember
that you don't include the quotation marks in response to the prompt.

\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, if there is one.
\item \texttt{front()}: Return the front item without removing
  it, if there is one.
\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+csc148_queue.py+ to implement the
    queue ADT.
  \item Download the file
    \href{http://www.cdf.toronto.edu/~heap/148/W14/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{enumerate}
\item Add code to \texttt{driver.py} so that it uses a queue after using a stack, and
  expects input lines to contain integers (except for the "end"
  line).  As before, it should stop accepting input when it sees the "end" string.
  \begin{itemize}
  \item Recall that you can convert an input line to an integer by
    calling the int constructor, \textbf{int(...)}
  \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/W14/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/W14/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 efficiency issue.

  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!

  If you do come up with a feasible solution in time, implement it in
  another file --- say \texttt{csc148\uline queue2.py}, and see
  whether the performance improves.  And of course, be sure to test
  your new implementation using \texttt{testqueue.py} --- efficiency
  at the cost of correctness is no bargain!
\end{enumerate}
Show your work to your TA before calling it a day!
\end{document}
