% -*- 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 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 8}
\cfoot{\thepage}
\rfoot{Due: 4:00pm, Friday, March 31}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\begin{question} \label{q:FFtime}
  \marginnote[0.2in]{\emph{\ref{q:FFtime}}\quad\qrcode{How\ many\
      times\ could\ the\ loop\ possibly\ execute?\ \ How\ long\ does\
      it\ take\ to\ find\ an\ augmenting\ path,\ augment\ the\ flow,\
      and\ compute\ a\ new\ residual\ network?}}  Explain in your own
  words how the Ford-Fulkerson algorithm can be implemented to run in
  $O(mC)$ time, where $m$ is the number of edges in the network and
  $C$ is the total capacity of all edges leaving the source node $s$.
\end{question}

\begin{question} \label{q:matching}
  Let $G = (V,E)$ be a bipartite graph with $V = L \cup R$ (that is,
  every edge in $G$ has one endpoint in $L$ and one in $R$).  A
  \emph{matching} in $G$ is a set of edges $M \subseteq E$ such that
  no two edges in $M$ share an endpoint.  A \emph{maximum matching} is
  a matching with the greatest possible number of edges.

  \marginnote{\emph{\ref{q:matching}}\quad\qrcode{Create\ a\ network\
      G'\ such\ that\ a\ maximum\ flow\ in\ G'\ corresponds\ to\ a\
      maximum\ matching\ in\ G.}} Design an algorithm to find a
  maximum matching in a given bipartite graph.  Describe your
  algorithm, prove its correctness, and analyze its running time.
\end{question}

\begin{question}[K\&T 7.6] \label{q:clients}
  Consider a set of mobile computing clients in a certain town who
  each need to be connected to one of several possible \emph{base
    stations}.  We'll suppose there are $n$ clients, with the position
  of each client specified by its $(x,y)$ coordinates in the plane.
  There are also $k$ base stations; the position of each of these is
  specified by $(x,y)$ coordinates as well.

  We wish to connect each client to exactly one of the base stations,
  but our choice of connections is constrained in the following ways.
  First, there is a \emph{range parameter}, denoted by $r$: a client
  can only be connected to a base station that is within distance $r$.
  There is also a \emph{load parameter} $L$: no more than $L$ clients
  can be connected to any single base station.

  \marginnote{\emph{\ref{q:clients}}\quad\qrcode{Again,\ create\ an\
      appropriate\ flow\ network.}}  Your goal is to design a
  polynomial-time algorithm for the following problem.  Given the
  positions of a set of clients and a set of base stations, as well as
  the range and load parameters $r$ and $L$, decide whether every
  client can be connected simultaneously to a base station, subject to
  the constraints $r$ and $L$.
\end{question}

\marginnote{The last 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.
  \begin{enumerate}
  \marginnote{\emph{\ref{q:amortized-practice}}\quad\qrcode{Start\ by\
      making\ tables\ of\ values\ and\ looking\ for\ patterns!}}
  \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$ 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{A 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
    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}.  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
%   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}
