
\documentclass[12pt]{article}
\usepackage{fullpage}

\newcommand{\falling}[2]{#1^{\underline{#2}}}
\newcommand{\rising}[2]{#1 ^{\overline{#2}}}
\newcommand{\stirling}[2]{\left\{ \begin{array}{c} #1 \\ #2 \end{array} \right\}}

\begin{document}
\begin{center}
\bf 
CS 141, Advanced Topics in Algorithms \\
Spring 2004\\
Homework 2b \\
Due Monday,  February 2 
\end{center}
\vspace{0.5cm}

\begin{enumerate}

\item \textbf{[20 Points] Proving the Correctness of the ``Real Queue - Helper Queue'' Data Structure.}
In class we considered an extension of the queue abstract data type, called a \emph{minqueue},
which supports operations ENQUEUE, DEQUEUE, and FINDMIN.  We  considered a clever data
structure for this abstract data type which works as follows:  There
are two regular queues used.  The first queue is called the ``real
queue'' and the second queue is called the ``helper queue''.  When the
ENQUEUE($x$) operation is performed, the element $x$ is enqueued in the
regular way on the real queue.  The element $x$ is also enqueued at the
end of the helper queue.  However, if the element $y$ immediately ``in
front'' of
$x$ on the helper queue is larger than $x$, then $y$ is removed from the
helper queue.  This process of $x$ annihilating the element immediately in
front of it is repeated until the element immediately in front of $x$ is
less than or equal to it or
$x$ is at the front of the helper queue.  To DEQUEUE an element, we remove it
from the real queue and, if that element is also at the head of the helper queue, we 
remove it from there as well.  Finally, FINDMIN simply returns the value at the head
of the helper queue.

In class we suggested an invariant for proving the correctness of this data structure.  State the invariant and then use it to prove formally that this data structure is correct.  (If you prefer to use a different invariant, you are welcome to do so.  Just make sure that your proof is correct!)

\item \textbf{[25 Points] Dictionaries.}
Problem 17-2 from Cormen \emph{et al.}, Second Edition.  This problem is attached
for your convenience.

\item \textbf{[30 Points] Weight-Balanced Trees!}
Problem 17-3 from Cormen \emph{et al.}, Second Edition.  This problem is attached for
your convenience.

\end{enumerate}
\end{document}



