% -*- compile-command: "rubber -d hw.8.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace}
\usepackage[linesnumbered,ruled]{algorithm2e}
% \usepackage[left=.75in,top=.75in,right=.75in,bottom=.75in]{geometry}

\usepackage{qrcode, enumitem}

\pagestyle{fancy}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}

\theoremstyle{definition}
\newtheorem{question}{Question}

\begin{document}

\lhead{CSCI 280: Algorithms -- Spring 2016}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 8}
\cfoot{\thepage}
\rfoot{Due: 4:00pm, Friday, April 8}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\marginnote{The 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.
  \begin{enumerate}
  \item $f(k)$ is the largest integer $i$ such that $2^i$ divides $k$.
  \item $f(k) = k$ if $k$ is a power of $2$, and $f(k) = 1$ otherwise.
  \item $f(k) = k$ is $k$ is a Fibonacci number, and $f(k) = 1$
    otherwise.
  \item Let $T$ be a \emph{complete} binary search tree, storing the
    integer keys $1$ through $n$. $f(k)$ is the number of 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}

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
\emph{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} and
  \textsc{Pop}.
\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
  global 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, insert
    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, insert
    everything into the new table, and then free the old table.
  \end{itemize}
  Show that for any sequence of insertions and deletions, the
  amortized time per operation is still
  $O(1)$.\marginnote{\emph{Hint}: Do not use potential functions.}
\end{question}

\end{document}
