% -*- compile-command: "rubber -d --unsafe hw-10-amortized.tex" -*-
\documentclass{tufte-handout}

\usepackage[num=10,date=November\ 25,dow=Monday,topic=Amortized\ analysis]{algorithms-hw}

\begin{document}

\coversheet

\marginnote{The first two questions on this problem set are due to Jeff
  Erickson:
  \url{http://www.cs.illinois.edu/~jeffe/teaching/algorithms}.}
\begin{question} \label{q:amortized-practice} Suppose we are
  maintaining a data structure under a series of $n$ operations. Let
  $f(k)$ denote the actual running time of the $k$th operation. For
  each of the following functions $f$, determine the resulting
  amortized cost of a single operation.  For amortized costs other
  than $\Theta(1)$, be sure to argue why your cost is also a \emph{lower}
  bound, \emph{i.e.}\ why it is not possible to do any better.

  Start by making tables of values and looking for patterns, and/or
  trying to write down a mathematical expression for the total cost
  $f(1) + f(2) + \dots + f(n)$.

  \begin{enumerate}[label=(\alph*)]
  \item \label{q:divpowtwo} $f(k)$ is the largest integer $i$ such that $k$ is evenly
    divisible by $2^i$.
    \marginnote{\emph{\ref{q:amortized-practice}\ref{q:powtwo}}\quad\qrcode{Where\
      have\ you\ seen\ a\ similar\ pattern\ before?}}
  \item \label{q:powtwo} $f(k) = k$ if $k$ is a power of $2$, and
    $f(k) = 1$ otherwise.
  \item $f(k) = k$ if $k$ is a Fibonacci number, and $f(k) = 1$
    otherwise.
  \item $f(k) = k$ if $k$ is a perfect square, and $f(k) = 1$ otherwise.
  \item \marginnote{Recall that a \emph{perfect} binary tree is one in which every node
      has two children and all leaves have the same depth.  Thus, a
      perfect binary tree with height $h$ has exactly $2^h - 1$
      nodes.}  Let $T$ be a \emph{perfect} binary search tree, storing
    the integer keys $1$ through $n$. $f(k)$ is the number of
    \emph{ancestors} of node $k$.
  \end{enumerate}
\end{question}

\begin{question} \label{q:extendable}
  An \emph{extendable array}
is a data structure that stores a sequence of items and supports the
following operations:
\begin{itemize}
\item $\textsc{AddToFront}(x)$ adds $x$ to the \emph{beginning} of the
  sequence.
\item $\textsc{AddToEnd}(x)$ adds $x$ to the \emph{end} of the sequence.
\item $\textsc{Lookup}(k)$ returns the $k$th item in the sequence, or
  \textsc{Null} if the current length of the sequence is less than
  $k$.
\end{itemize}

\marginnote{\emph{\ref{q:extendable}}\quad\qrcode{Use\ two\ arrays.}}
Describe and analyze a \emph{simple} data structure that implements an
extendable array. Your \textsc{AddToFront} and \textsc{AddToBack}
algorithms should take $O(1)$ \emph{amortized} time, and your
\textsc{Lookup} algorithm should take $O(1)$ \emph{worst-case}
time. The data structure should use $O(n)$ space, where $n$ is the
current length of the sequence.
\end{question}

\begin{question}
  Describe how to implement a queue using two stacks and $O(1)$
  additional memory, so that the amortized time for any enqueue or
  dequeue operation is $O(1)$. The \emph{only} access you have to the
  stacks is through the standard methods \textsc{Push}, \textsc{Pop},
  and \textsc{IsEmpty}.  You may assume that \textsc{Push} and
  \textsc{Pop} take $O(1)$ time in the worst case.
\end{question}

\begin{question}
  Suppose we can insert or delete an element into a hash table in
  $O(1)$ time.  In order to ensure that our hash table is always big
  enough, without wasting a lot of memory, we will use the following
  rebuilding rules:
  \begin{itemize}
  \item After an insertion, if the table is more than $3/4$ full, we
    allocate a new table twice as big as our current table, reinsert
    everything into the new table, and then free the old table.
  \item After a deletion, if the table is less than $1/4$ full, we
    allocate a new table half as big as our current table, reinsert
    everything into the new table, and then free the old table.
  \end{itemize}
  Show that for \emph{any} sequence of insertions and deletions, the
  amortized time per operation is still $O(1)$.
\end{question}

\end{document}
