% ---------
% Compile with “pdflatex hw0”.
% --------
%!TEX TS-program = pdflatex
%!TEX encoding = UTF-8 Unicode
\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools}
\usepackage[mathletters]{ucs} % define text Greek letters; load BEFORE inputenc
\usepackage[utf8x]{inputenc} % Allow some non-ASCII Unicode in source
\usepackage{fourier-orns}
\usepackage{eucal}
\usepackage{enumerate}
\usepackage{stmaryrd}
\usepackage{pifont}
\def\Spade{\text{\ding{171}}}
\def\Heart{\text{\textcolor{Red}{\ding{170}}}}
\def\Diamond{\text{\textcolor{Red}{\ding{169}}}}
\def\Club{\text{\ding{168}}}
%\hidesolutions
% ======================================================
\begin{document}
\headers{CS 473}{Homework 6 (due March 15)}{Spring 2016}
\thispagestyle{empty}
\begin{center}
\Large\textbf{CS 473 \,\decosix\, Spring 2016}%
\\
\LARGE \textbf{\decothreeleft~ Homework 6 ~\decothreeright}
\\[0.5ex]
\large Due Tuesday, March 15, 2016, at 8pm
\end{center}
\hrule
\bigskip
\noindent
For problems that use maximum flows as a black box, a full-credit solution requires the following.
\begin{itemize}
\item
A complete description of the relevant flow network, specifying the set of vertices, the set of edges (being careful about direction), the source and target vertices $s$ and $t$, and the capacity of every edge. (If the flow network is part of the original input, just say that.)
\item
A description of the algorithm to construct this flow network from the stated input. This could be as simple as “We can construct the flow network in $O(n^3)$ time by brute force.”
\item
A description of the algorithm to extract the answer to the stated problem from the maximum flow. This could be as simple as “Return \textsc{True} if the maximum flow value is at least $42$ and \text{False} otherwise.”
\item
A proof that your reduction is correct. This proof will almost always have two components. For example, if your algorithm returns a boolean, you should prove that its \textsc{True} answers are correct and that its \textsc{False} answers are correct. If your algorithm returns a number, you should prove that number is neither too large nor too small.
\item
The running time of the overall algorithm, expressed as a function of the original input parameters, not just the number of vertices and edges in your flow network.
\item
You may assume that maximum flows can be computed in $O(VE)$ time. Do \emph{not} regurgitate the maximum flow algorithm itself.
\end{itemize}
Reductions to other flow-based algorithms described in class or in the notes (for example: edge-disjoint paths, maximum bipartite matching, minimum-cost circulation) or to other standard graph problems (for example: reachability, minimum spanning tree, shortest paths) have similar requirements.
\bigskip
\hrule
\bigskip
\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.5fil
\item
Suppose you are given a directed graph $G=(V,E)$, two vertices $s$ and~$t$ in $V$, a capacity function $c\colon E\to\Real^+$, and a second function $f\colon E\to\Real$. Describe an algorithm to determine whether $f$ is a maximum $(s,t)$-flow in $G$. Do not assume \EMPH{anything} about the function $f$.
\item
Suppose you have already computed a maximum flow $f^*$ in a flow network $G$ with \EMPH{integer} edge capacities.
\begin{enumerate}
\item
Describe and analyze an algorithm to update the maximum flow after the capacity of a single edge is increased by $1$.
\item
Describe and analyze an algorithm to update the maximum flow after the capacity of a single edge is decreased by $1$.
\end{enumerate}
Both algorithms should be significantly faster than recomputing the maximum flow from scratch.
% Later
%\item
%Describe and analyze an algorithm to determine, given an undirected graph $G = (V, E)$ and three vertices $u, v, w \in V$ as input, whether $G$ contains a simple path from $u$ to $w$ that passes through $v$.
\newpage
\item
Suppose you are given an $n\times n$ checkerboard with some of the squares deleted. You have a large set of dominos, just the right size to cover two squares of the checkerboard. Describe and analyze an algorithm to determine whether it is possible to tile the board with dominos—each domino must cover exactly two undeleted squares, and each undeleted square must be covered by exactly one domino.
\begin{center}
\includegraphics[scale=0.35]{../notes/Fig/deleted-grid}
\end{center}
Your input is a two-dimensional array $\emph{Deleted}[1\,..\,n,1\,..\,n]$ of bits, where $\emph{Deleted}[i,j] = \textsc{True}$ if and only if the square in row $i$ and column $j$ has been deleted. Your output is a single bit; you do \EMPH{not} have to compute the actual placement of dominos. For example, for the board shown above, your algorithm should return \textsc{True}.
\end{enumerate}
\end{document}