\documentstyle{6.170-ps}

\psnum{1}
\duedate{Monday, September 18, 1989}
\handedoutdate{Tuesday, September 12, 1989}
\handoutnumber{4}
\pstitle{Using Data Abstractions}
\name{Marc Horowitz}
\design{15 minutes}{20 minutes}{3}
\implementation{30 minutes}{30 minutes}{8}
\testing{30 minutes}{120 minutes}{4}
\documentation{30 minutes}{60 minutes}{5}
\date{Monday, September 18, 1989}
\TARF

\begin{document}
\makecover
\newpage

\maketitle

\section{Problem Specification Amendments}
The specifications given in the book do not give a specific form for
the outputted breadth-first lists.  In my implementation, I chose to
print each level of the tree on a separate line.  For example, 
\begin{picture}(100,50)
\put(50,45){\makebox(0,0){1}}
\put(26,24){\makebox(0,0){2}}
\put(74,24){\makebox(0,0){5}}
\put(10,3){\makebox(0,0){3}}
\put(42,3){\makebox(0,0){4}}
\put(58,3){\makebox(0,0){6}}
\put(90,3){\makebox(0,0){7}}

\put(50,40){\vector(-3,-2){19}}
\put(50,40){\vector(3,-2){19}}
\put(26,19){\vector(-1,-1){12}}
\put(26,19){\vector(1,-1){12}}
\put(74,19){\vector(-1,-1){12}}
\put(74,19){\vector(1,-1){12}}
\end{picture}
would be printed as
\begin{tabular}[b]{l} 1 \\ 2 5 \\ 3 4 6 7 \end{tabular}.

\newpage

\section{Design Documentation}

\subsection{Overview}

The two programs are quite simple, designed to test the breadth-first
routines.  Each program has a \verb+start_up+ procedure which calls
the list routine several times with several test trees or digraphs.

Originally, I designed my code to print the entire list on one line.
After printing several tests, I decided that this was both
aesthetically unpleasing and not very useful.  This code was written
to deal with only trees at first.

In the next implementation, I used two queues to print each depth on
a separate line.  I created a queue \verb+thisline+ and added the
node number \verb+n+ which was passed in to the procedure.  The main
loop checks to see if \verb+thisline+ is empty.  If it is, the
procedure ends.  If not, the queue \verb+lastline+ is created and set
equal to \verb+thisline+.  The inner loop prints each member of
\verb+lastline+ and adds its children to \verb+thisline+.  The loop is
repeated until the new line contains no elements.

To write \verb+breadth_first_graph+, all that was necessary was to
maintain an intset of visited nodes.  The initial node is added to the
intset of visited nodes.  Each node is added to the intset when it is
displayed.  In the inner loop, a node is added to \verb+thisline+ only
if it had not been visited before.

\subsection{Module Specifications}

\subsubsection{\protect{\verb+breadth\_first\_tree+}}
\input breadth_first_tree.spec

\subsubsection{\protect{\verb+breadth\_first\_graph+}}
\input breadth_first_graph.spec

\newpage

\section{Program Listings}
\subsection{\protect{\verb+breadth\_first\_tree+}}
\input breadth_first_tree.tex

\subsection{\protect{\verb+breadth\_first\_graph+}}
\input breadth_first_graph.tex

\newpage

\section{Testing Description and Output}
The trees and graphs I built for testing are intended to test boundary
cases, average cases, and complex cases.

\subsection{Description}

For \verb+breadth_first_tree+, I used four test trees.  The first
consists of just one element.  The second is a simple binary tree.
The third is a straight line of nodes with one child each.  The fourth
is complex, including nodes with anywhere from zero to three children
at several depths.  I printed lists of all of these trees from the
root, and printed a list of the fourth tree from a node not the root.
The first and third cases are are intended to test boundary cases of no
children or just one.  The second case is a normal case, and the
fourth is supposed to be big and heinous.

For \verb+breadth_first_graph+, I used four graphs.  The first, again,
is just one node.  The second is the same as the most complex tree
from the previous set of tests.  The third is a ring of five nodes,
which I printed from two different points.  The fourth was a
complex graph, with two disjoint sets of nodes, each pointing back
upon itself several times.  This was printed from several different
places.  The first case is a boundary condition.  The second and is
simple normal input.  The third will test routines which do not handle
remembering visited nodes correctly.  (This test caught an error in my
code, actually.)  The fourth case tests everything, containing two
disjoint pieces, several interconnected nodes, and nodes unreachable
one direction, but reachable the other.

\subsection{Output}

\subsubsection{\protect{\verb+breadth\_first\_tree+}}
\input breadth_first_tree.test

\subsubsection{\protect{\verb+breadth\_first\_graph+}}
\input breadth_first_graph.test


\end{document}
