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

\newcommand{\assignmentNumber}{4}
\newcommand{\outdate}{29 September, 1994}
\newcommand{\duedate}{11 October, 1994}

\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}
Practice in deletion in linked list, an introduction to
the analysis of algorithms, and to heuristics in algorithm
design.

\subsection*{Reading Assignment}
Read chapters 13 and 14 in {\em Condensed Pascal.} Chapter 13,
Analysis of Algorithms, places in a larger context the
in class discussion of the unique words program's quadratic
run time.
Chapter 14 discusses preconditions, postconditions and invariants.

\subsection*{Programming Assignment}

The unique words program of Problem Set 3 scans the list of
unique words for each new word encountered. The most common
words occur soon after the beginning of the text, and hence
are found near the end of the list. For this reason, the
program runs slowly.

A {\em heuristic} is an algorithm which
tends to work although cannot be guaranteed to work.
The {\em move-to-front}\/ heuristic tries to optimize the
list of words, moving popular words to the front of the list.
It does this automatically. Each time a word is matched on
the list, it is removed from its current position and
reinserted at the head of the list.

This algorithm is only a heuristic.
It can be made to work poorly on diabolically designed data
sets, but never worse than a factor of two compared to our
old algorithm. On typical inputs, the common words will cluster 
at the front of the list, improving by a large factor
the time required to find a majority of the words.

\end{document}
