\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage[all]{xy}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2004\\
\rm
Homework 11a\\
Due on Thursday, 11/12/2004 (beginning of class)\\
\end{center}
\begin{enumerate}
\item \textbf{[20 Points] Walking In the Network-Flow!}

This problem aims to increase your familiarity with Network-Flow flow
graphs---in particular, how capacities, flows, and their constraints change over
time as flow is repeatedly pushed along edges for which a path in the residual
graph exists. This problem is explained more thoroughly in the accompanying 
hand-drawn sheets. You should not turn in a Latex copy of your work for this
problem---rather use the Xeroxes provided to fill in your answers.

%THINGS TO CHANGE
%A) Use the term ``movie''.
%
%B) Indicate that students should:
%    1) clearly specify which trace they're doing (BFS, DFS) in each ``movie''.
%    2) clearly state the final |f| obtained for each.
%    3) clearly state how DFS and BFS path augmentation behave:
%         DFS: When choosing the next augmenting path, start at s, go
%         thru the edge lists in a depth-first order, and continue 
%         traversing until t is first found.
%         BFS: Do the same exact thing but in a breadth-first manner: you keep going
%         until the first path from s to t is found.
%       for each augmenting path, this procedure starts from scratch.
%
%C) Fantasy time: expand the writeup in to Latex (blech!)
%\begin{center}
%\begin{tabular}{ccc}
%\begin{minipage}{2.5in}
%\xymatrix{
%                                           & A \ar@{->}[d]^{\bf 1} \ar@{->}[dr]^{\bf 4} & \\
%s \ar@{->}[ru]^{\bf 3} \ar@{->}[r]_{\bf 1} & B \ar@{->}[r]_{\bf 1} \ar@{->}[u]^{\bf 1}  & t }
%\end{minipage}
%&\hspace*{.5in}&
%\begin{minipage}{2.5in}
%\begin{tabular}{|c|cccc} \cline{1-1}
%$s$ & $\rightarrow$ & $A$ & $\rightarrow$ & $B$ \\ \cline{1-1}
%$A$ & $\rightarrow$ & $B$ & $\rightarrow$ & $t$ \\ \cline{1-1}
%$B$ & $\rightarrow$ & $t$ & $\rightarrow$ & $A$ \\ \cline{1-1}
%$t$ & &\\ \cline{1-1}
%\end{tabular}
%\end{minipage}
%\end{tabular}
%\end{center}


\item \textbf{[14 Points] Review of Network Flow Proofs.}

In class, we'll be proving four fundamental theorems which, in the end, will
allow us to show that the network flow algorithms that we will see next time
do indeed find maximum flows from $s$ to $t$.  For this
assignment, you will re-prove the first three theorems, which we saw in class today:

\begin{enumerate}
\item The Cut Theorem
\item The Capacity Theorem
\item The Max-Flow Min-Cut Theorem
\end{enumerate}

The proofs used in class are easier than those given in the book.  Your task is
to carefully reconstruct the arguments {\bf made in class!}  Your grade in this
problem will be based largely on how clearly and precisely you write your
proofs.







\end{enumerate}
\end{document}
