\documentstyle[12pt]{report}
\pagestyle{myheadings}
\def\headlineaux{\sc Math 220/317: Programming II/Data Structures
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\newcommand{\assignmentNumber}{3}
\newcommand{\outdate}{5 October, 1992}
\newcommand{\duedate}{12 October, 1992}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge  Burt Rosenberg }
\end{centerline}\end{titlepage}

\subsection*{Problem Set 3 Notes}

The output of ps3a.pas and ps3b.pas should be:
\begin{enumerate}
\item The words in the file, in reverse order of their first occurrence,
  and with each word, the number of
  times it appears in the file.
\item A count of the total number of words in the file.
\item A count of the total number of unique words in the file.
\item The total number of elements that were searched during the program.
\end{enumerate}

For example, the file:
\[\mbox{ one fish two fish red fish blue fish }\]
gives the output:
\begin{verbatim}
  8 words in the text
  5 unique, they are:
  1 blue
  1 red
  1 two
  4 fish
  1 one
 27 elements searched
\end{verbatim}
Let's go through this example in detail. 
We will keep the total number of elements searched in the
count field of the dummy header. Before reading any words,
the list is,
\[ \mbox{ (X, 0) } \]
Where we represent a record by (str,cnt).
The word ``one'' was read, the list
was searched and one was inserted at its head. (We will count the dummy header element),
\[ \mbox{ (X, 1) } \longrightarrow
   \mbox{ (one, 1) } \]
``Fish'' is read, the list searched and fish inserted at its
head. The list was two long before the insertion of fish, so
the new number of total searches is 3,
\[ \mbox{ (X, 3) } \longrightarrow
    \mbox{ (fish, 1) } \longrightarrow
   \mbox{ (one, 1) } \] 
``Two'' was inserted at the head after the
unsuccesful search of a three element list so now,
\[ \mbox{ (X, 6) } \longrightarrow
    \mbox{ (two, 1) } \longrightarrow
    \mbox{ (fish, 1) } \longrightarrow
   \mbox{ (one, 1) } \] 
When the
second ``fish'' was read, the program found that fish was the third element
in the list, counting the dummy header node,
\[ \mbox{ (X, 9) } \longrightarrow
    \mbox{ (two, 1) } \longrightarrow
    \mbox{ (fish, 2) } \longrightarrow
   \mbox{ (one, 1) } \] 
``Red'' was tacked on the the front after an 
unsuccessful search of a 4 element
list,
\[ \mbox{ (X, 13) } \longrightarrow
  \mbox{ (red,1) } \longrightarrow
    \mbox{ (two, 1) } \longrightarrow
    \mbox{ (fish, 2) } \longrightarrow
   \mbox{ (one, 1) } \] 
The third ``fish'' was found buried as the fourth
element of the list,
 \[ \mbox{ (X, 17) } \longrightarrow
  \mbox{ (red,1) } \longrightarrow
    \mbox{ (two, 1) } \longrightarrow
    \mbox{ (fish, 3) } \longrightarrow
   \mbox{ (one, 1) } \] 
``Blue'' was
added to the front of a 5 element list,
\[ \mbox{ (X, 22) } \longrightarrow
  \mbox{ (blue,1) }\longrightarrow
  \mbox{ (red,1) } \longrightarrow
    \mbox{ (two, 1) } \longrightarrow
    \mbox{ (fish, 3) } \longrightarrow
   \mbox{ (one, 1)} \] 
The final ``fish'' was found 5 elements from the list root,
\[ \mbox{ (X, 27) } \longrightarrow
  \mbox{( blue,1) }\longrightarrow
  \mbox{ (red,1) } \longrightarrow
    \mbox{ (two, 1) } \longrightarrow
    \mbox{ (fish, 4) } \longrightarrow
   \mbox{ (one, 1) } \] 

\end{document}
