\documentclass[12pt]{article}
\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 182} \\ Advanced Topics in Algorithms \\ Spring 2003 \\
Problem Set 2b \\ Due Tuesday, February 4
\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.}
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{[15 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$.  (Recall that load is defined to be the number of elements in the array divided by the size of the array.)
Now consider a different policy in which
we contract the array by reducing it to $2/3$ its current size when the
load drops below
$1/3$.   However, on an INSERT, we still simply double the array size when it overflows.
Use the potential function
\[
\Phi(A) = | 2 \times \mbox{num}(A) - \mbox{size}(A)|
\]
to show that the amortized cost of each INSERT and DELETE operation is bounded
by a constant.  (You can appeal to anything we did in class to save yourself some work.)

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

\item \textbf{[25 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}