\documentstyle[12pt]{article}
\textheight=9.5in
\topmargin=-0.5in
\oddsidemargin=0in
\evensidemargin=0in
\textwidth=6.5in
\newcommand{\grad}{\nabla}
\newcommand{\spone}{1.02}
\newcommand{\sptwo}{1.59}
\newcommand{\spmed}{1.28}
\newcommand{\singlespace}{\edef\baselinestretch{\spone}\Large\normalsize}
\newcommand{\doublespace}{\edef\baselinestretch{\sptwo}\Large\normalsize}
\newcommand{\mediumspace}{\edef\baselinestretch{\spmed}\Large\normalsize}
\newcommand{\beq}{\begin{displaymath}}
\newcommand{\be}{\begin{equation}}
\newcommand{\eeq}{\end{displaymath}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}{\begin{flushleft}}
\newcommand{\el}{\end{flushleft}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\La}{\Longleftarrow}
\newcommand{\la}{\langle}
\newcommand{\Ra}{\Longrightarrow}
\newcommand{\ra}{\rangle}
\newcommand{\Ba}{\Longleftrightarrow}
\newcommand{\goto}{\rightarrow}
\pagestyle{empty}
\begin{document}
\begin{center}
\fbox{\bf An Example of Hash Coding}
\end{center}
\vspace{0.25in}

Suppose you are creating a list of objects sequentially and you need to
avoid listing duplicates. One possible way to do this is simply to check
the list created so far to make sure the currrently tested item has not
appeared previously. However, for a list of $N$ items, this would require
$N(N-1)/2$ operations. We can avoid the large cost by using {\em hash
coding}:
\vspace{0.1in}

\begin{description}
\item[0.] Decide on a way to associate a {\em label} with each item
          whose prior presence on the list can be {\em easily} checked
	  (i.e., by {\cal O}(1) operations regardless of the length of
          the list).
\item[1.] Put the first item on the list and mark its {\em label} to be
          on the list.
	  \vspace{0.1in}

          (At this point, only 1 item is associated with the particular
          {\em label}; so it is easy to put the reverse identification of
          {\em label} $\Longrightarrow$ the item.)
\item[2.] Pick the next item and test if its {\em label} is already on the
	  list. You do this by looking up item(s) associated with the same
          {\em label} and examining it (them) only (not the whole list).
	  \vspace{0.1in}

          (If there are multiple items with the same {\em label},
          you can set up an auxiliary pointer tree which starts from the
          item most recently associated with the {\em label} and points
          in a {\em chainlike} manner toward the oldest such item.)
 \begin{itemize}
  \item If yes, discard the item and repeat {\bf 2}.
  \item If no, put the item on the list and mark its {\em label} to be
        on the list. Then repeat {\bf 2}.
        \vspace{0.1in}

        (Either set up the reverse identification {\em label} $\Longrightarrow$
        to the item if there is only one item with this {\em label}, or
        continue with the pointer tree if there are now more than one such
        item.)
 \end{itemize}
\item[3.] Stop when an appropriate stopping criterion is satisfied (a
          predetermined size of the list or no more items left due to the
          item creation/search algorithm in most cases).
\end{description}
\end{document}
