% -*- 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}