\documentclass[12pt]{article}
\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\usepackage{graphicx}
% \usepackage{geometry}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2007 \\
	\rm
	Homework 9a\\
	Due Thursday, March 29
\end{center}

You are encouraged to register and compete in the upcoming TopCoder competition.  This is an on-line programming contest that emphasizes algorithm design and implementation.  Dynamic programming, graph algorithms, divide-and-conquer, greed, and snazzy data structures are often key features of these contests.  Several current and former HMC algorithms students have competed and a few have won very large cash prizes!

The next major contest has a registration deadline of Tuesday, March 27 at 5 PM.  The contests are then on March 29, March 31, and April 3.  You need only sign up for one contest and the contest takes a couple of hours.

If you compete in one of these three TopCoder contests, you can opt out of 25 points worth of problems on the upcoming Assignment 9b \textbf{or} you can claim 25 bonus points in this course.  You just need to send me e-mail telling me that you participated and write 3 or 4 sentences indicating what problems you worked on and how it went.

\begin{enumerate}

\item \Points{10} \Name{Trying out the Ford-Fulkerson Network Flow Algorithm.}
Consider the flow network shown below where the the source is  $s$, the sink is $t$, and the numbers on the edges indicate capacities.
\begin{figure}[htbp]
\begin{center}
\includegraphics[height=1.5in]{network.pdf}
\end{center}
\end{figure}
\begin{enumerate}
	\item Using a cut in this network, explain briefly but convincingly why no flow in this network can possibly have a value higher than $5$.
	\item Now, show each iteration of  the Ford-Fulkerson algorithm on this graph.  \textbf{Assume that the first augmenting path found is the path $s, a, c, t$.}  (You can decide which augmenting paths are found at the subsequent iterations.)  For each iteration draw two pictures:  First show the augmenting path for that iteration and then show the residual network after that augmenting path is used to increase the flow.
 	\item Now draw the network again, indicating the final maximum flow found by the algorithm.  The picture should look like the one above, but each edge should have a label of the form $x/y$ where $x$ indicates the flow on that edge and $y$ indicates the original capacity of that edge.  For this particular drawing, don't show the negative flows.
	
		\item Show the set of vertices that can be reached from $s$ in the last residual graph.  Explain how this set defines a cut and show that the capacity across this cut is $5$.
	
\end{enumerate}
\item \Points{20} \Name{Review of Network Flow Proofs.}
In class we proved four fundamental theorems, culminating in the ``Greed is Good'' Theorem which asserts that the Ford-Fulkerson Algorithm does indeed find a maximum flow from $s$ to $t$.  These four theorems were:
 \begin{enumerate}
   \item The Cut Theorem
   \item The Capacity Theorem
   \item The Max-Flow Min-Cut Theorem
   \item The ``Greed is Good'' Theorem for Network Flows
 \end{enumerate}
Your task is to carefully write out the proofs of each of these 
four theorems as presented in class.  Your grade will be based largely on
how clearly and precisely you write your proofs.
\end{enumerate}

 \end{document}