\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 \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Problem Set \assignmentNumber \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Out: \outdate
     \\ Due: \duedate\end{flushright}}}}


\subsection*{Reading Assignment}
Read 
\begin{itemize}
\item Chapter 3, Sections
 ``Programming with Linked Lists'' and ``Variations of the Linked List''.
\item Chapter 4, Sections ``Abstraction'' and ``Abstract Data Types''.
\end{itemize}

\subsection*{Goals}
More practice using pointers and linked lists: dummy header technique,
searching a linked list and
moving elements in a list. Introduction to code
instrumentation.

\subsection*{Assignment}
You will write two programs, modifications of last week's assignment.
The first program, {\em ps3a.pas}, will use a linked list with a
dummy header element to
keep track of all the words in the file {\em datafile.dat} and for each
word a count of how many times that word appears in {\em datafile.dat}.
This program will be a modification of last week's {\em ps2.pas}.
In {\em ps3b.pas}, the second program, we will attempt to improve the performance of
{\em ps3a.pas} by using the move-to-front heuristic.

The output will include,
\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}

Many people write too much code before testing. It is often hard
to know where to break a large programming assignment into steps.
The following step-by-step instructions will help you organize your progress.

%\subsubsection*{Assignment Step-by-step}
\begin{enumerate}
\item Copy {\em [.ps2]ps2.pas} to {\em [.ps3]ps3a.pas} and modify the
  list subroutines to use a dummy header element. Test that
  the program gives the same outputs as ps2.pas.
\item Write functions
\begin{eqnarray*}
 \mbox{eq\_string}(s,t) &=& \left\{
  \begin{array}{ll} T & s=t, \mbox{ with $s, t$ of stringType}
  \\ F & \mbox{else.}
  \end{array}\right.
\\
  \mbox{search\_list}(l,s) &=& \left\{
   \begin{array}{ll} p & p\wedge.\mbox{next}\wedge.\mbox{str} =s \\
   \mbox{nil} & \mbox{else.}
   \end{array}\right.
\end{eqnarray*}
  Change your main-line program to use search\_list to insert an
  element only if it has not be found in the list. Test 
  thoroughly before proceeding!
\item Finish ps3a.pas by writing subroutines,
\begin{verbatim}
  procedure increment_count( p:listPntr ) ;
    {increments p^.next^.cnt}
  function length_list( l:listPntr ) :integer ;
    {returns length of list l, except header}
  function sum_count( l:listPntr ) :integer ;
    {returns sum of all p^.cnt in l, except header}
\end{verbatim}
  Modify create\_list and search\_list to keep track of
  the total number of elements searched.
  Test your finished {\em ps3a.pas} on several inputs, both
  long and short.
\item Copy {\em ps3a.pas} to {\em ps3b.pas} and continue. Write,
\begin{verbatim}
  procedure move_to_front( l,p:listPntr )
\end{verbatim}
  which takes element p and from its current position in list l and
  moves it to the front. Modify the main-line program to use
  this procedure to implement the move-to-front search heuristic. Test
  this program on several inputs and compare the number of searched
  elements made by this program with the number made by ps3a.pas.
\end{enumerate}

\end{document}
