\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 2009 \\
	\rm
	Homework 9a\\
	Due Thursday, March 26
\end{center}

\begin{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}
For each theorem, first state precisely what the theorem says and then give a clear and rigorous proof. 

\item \Points{15} \Name{Graph Partitioning!}
Given an \emph{undirected} graph $G$, a \emph{partition} of the graph is a division of the vertices
into two sets $A$ and $B$ such that every vertex is in exactly one of $A$ and $B$.  
The only constraint on $A$ and $B$ is that neither set can be empty. 
The  \emph{crossing number} of the partition is the number of edges with one endpoint in $A$ and one
endpoint in $B$.  Your job is to find an algorithm that finds a partition with the
smallest possible crossing number. 
(Fast graph partitioning algorithms are used in a wide variety of applications ranging from data clustering in machine learning to circuit design.)

\begin{enumerate}
  \item Describe your algorithm.  (You may use existing algorithms to help!)
  \item Prove that your algorithm is correct.
  \item Derive the running time of your algorithm.  It must be polynomial in the number of vertices and edges in the graph.
\end{enumerate}


		
\end{enumerate}

 \end{document}