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

\newcommand{\assignmentNumber}{5}
\newcommand{\outdate}{23 September, 1993}
\newcommand{\duedate}{1 October, 1993}

\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*{Goals}
Perfection in understanding and manipulating linked lists.

\subsection*{Reading Assignment}
Read Chapter 4 from {\em Algorithms.} This pertains to the class
discussion on Trees.

\subsection*{Programming Assignment}
Last week's program is too slow! The problem is that
the length of a search depends linearly on
the depth of the found item, meanwhile, under the insert-at-head
scheme, common words such as ``a'' and ``the'' tend to be
at the end of the list! Let's remedy this incongruity.

There are two approaches. Both are heuristics.
A {\em heuristic} is an algorithm which
tends to work although cannot be guarantied to work.
Your assignment is to implement the {\em move-to-front}\/ heuristic.
For extra credit, also implement
the {\em insert-at-tail}\/ heuristic, test, 
compare and comment on relative performance.

Move-to-front acts the same as insert-at-head for words not
found in the list --- they are added to the head of the list.
However, if a word is on the list, move-to-front increments
its count {\em and} moves the word to the head of the list.
Common words thus always cluster around the list's head.

\newcommand{\prettysymbol}{\Diamond}
\[ \prettysymbol \hspace{1in} \prettysymbol \hspace{1in} \prettysymbol \]

{\sc Extra Credit:}
In insert-at-tail, new words are inserted at the end of the
list, rather than its head. 
The tendency will now be for unusual words to find themselves at the
back of the list.
However, a diabolically constructed file, such as
a long text file with the words sorted, will make insert-at-tail
run {\em worse} than insert-at-head. But OK, that's why
it is called a {\em heuristic}.

The insert-at-tail
implementation will require some rethinking the list data-type.
We are all interested to see what you come up with!

\end{document}
