\documentclass[12pt]{article}
\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 181b} \\ Advanced Topics in Algorithms \\ Spring 2002 \\
Problem Set 1b \\ Due Tuesday, January 29 in class
\end{center}

Please remember that all problem set submissions must be typeset,
preferably in \LaTeX.  Please keep an electronic version of your
solution set for your records.

\begin{enumerate}
\item \textbf{[10 Points] The Arithmetic and Geometric Mean.}
This problem is a good review of the subtleties of mathematical induction.
It's also a result that we'll be using in class next week!

Let $x_{1}, \ldots, x_{n}$ be positive real numbers.  The {\em arithmetic
mean} of these numbers is defined to be $\frac{x_{1} + x_{2} + \ldots + x_{n}}{n
}$ and the {\em geometric mean} is defined to be 
$(x_{1}x_{2} \cdots x_{n})^{1/n}$.
In this problem we show that the arithmetic mean of $n$ numbers is at least
as large as the geometric mean of those numbers.
        \begin{enumerate}
        \item Use induction to show that if $x_{1} x_{2} \cdots x_{n} = 1$ 
        then $x_{1} + x_{2} + \ldots + x_{n} \geq n$.
        Observe that this is a special case of the statement we are trying
        to prove.
        \item Use this fact to show that the arithmetic mean is at least
        as large as the geometric mean.  (No induction required here; just
        a little algebra.)
        \end{enumerate}

\item \textbf{[10 Points] Binary Counters with Reset!}
Consider the binary counter problem that we examined in class.
The counter starts at 0.  In addition to the INCREMENT operation, we
also wish to support the RESET operation which resets the counter to 0.
Show that any sequence of INCREMENT and RESET operations can be performed
in $O(n)$ time.  (\emph{Hint:}  Keep a pointer to the high-order 1.)

\item \textbf{[10 Points] Extendible Arrays Revisited.}
In class we examined extendible arrays with operations INSERT and DELETE.
In particular, our rule for DELETE was that the array gets halved
when the load drops below $1/4$.  Now consider a different policy in which
we contract the array by $2/3$ when the load drops below $1/3$.
Use the potential function
\[
\Phi(A) = | 2 \times \mbox{num}(T) - \mbox{size}(T)|
\]
to show that the amortized cost of a DELETE operation is bounded
by a constant.

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

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


\end{enumerate}
\end{document}