\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,url}
\usepackage{bbm}
\usepackage{hyperref}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Professor John Tomlin (jtomlin5@stanford.edu) }
{\\ \bssten HW\#1 --  Due Tuesday 01/29/13}
\vspace{5pt}

\begin{enumerate}

\item 
Let $G=(V,E)$ be a graph with $|V|=n$ vertices and $|E|=m$ edges. Let $(C_i)_{i\in E}$ be the capacity of each edge. You can assume that the capacities are integers. Compute the complexity of the Ford-Fulkerson algorithm described in class.

Show a simple graph where the Ford Fulkerson algorithm performs poorly. Explains how many steps are required.

Try to find a better algorithm. What is its complexity? How does it perform on the previously mentionned graph?

\item 
You will apply the max-flow min-cut theorem to solve standard problems.

\begin{enumerate}
\item 
Perfect matching in a bipartite graph : 

A \textbf{bipartite graph} is a graph whose vertices can be divided in two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to a vertex in $V$.

A bipartite graph has a \textbf{perfect matching} if there is a set of edges $S\subset E$ such that every vertex belongs to exactly one edge of $S$. In other words, for a bipartite graph, if there are $n$ vertices in $U$ and $n$ vertices in $V$, there is a perfect matching if there are $n$ edges such that no two edges have a vertex in common. (Note that the definition of a perfect matching extends beyond just bipartite graphs)

By applying the max-flow min-cut algorithm, devise a way to determine whether a bipartite graph has a perfect matching or not.

\item
Project selection :

\begin{itemize}
\item There is a set of $n$ projects $P_{1}... P_{n}$
\item There are rewards for each project $R_{1}... R_{n}$. $R_{i} \geq 0$ if the corresponding project is a revenue. $R_{i} \leq 0$ if the corresponding project is a cost.
\item The projects have dependencies a project can be a prerequisite of another.
\end{itemize}
The goal is to choose the set of projects $S$ that maximizes the total reward while respecting the dependencies. (i.e $max_{S \in E} \sum\limits_{i \in S} R_{i}$ such that the dependencies are respected)

Explain how, by using the max-flow min-cut algorithm, you can find the best subset of projects.

\end{enumerate}

\item Implementation of the max-flow min-cut algorithm

In this exercise, you will implement the max-flow min-cut algorithm, and test it on cases that will be provided to you. The choice of the programming language is free, but comments are mandatory in your code. You are also free to implement the flow algorithm of your choice, may it be the one provided in class, or another more efficient one. Please, print out your code and attach it to your Assignment. You will need to download files on the Piazza course website (you may need to register at \url{https://piazza.com} if you still haven't done it)

For this exercise, we will consider a simpler version of the max-flow min-cut algorithm. You can consider that capacities are always integers, there is only one source and one sink. Also, note that the edges are "symmetric" : for each edge going from vertex $i$ to $j$ with capacity $c$, there is an edge from $j$ to $i$ also with capacity $c$.

\begin{enumerate}
\item First, we will describe how the network is stored in memory. The files start with $n$ lines containing 2 numbers each. These are the coordinates of the $n$ vertices. Then, the file contains $m$ lines with 3 numbers each, that correspond to each of the $m$ edges. These numbers correspond respectively to the source vertex index, target vertex index and capacity of the edge.

Open the file \textbf{data\_6.txt}. The first 6 lines contain 2 values separated by a tabulation. Note that the vertex described on the first line is the vertex 0, the one on the second line is the vertex 1, etc... until you reach on the sixth line the vertex 5. You do not need the coordinates of the vertices for this exercise. they only are useful is you want to have a visual representation.

Then, each line of the file contains a description of an edge. The line : 
$0 \> \> 5 \> \> 90$ 
means that there is an edge from vertex 0 to vertex 5 with capacity 90.

You can open the file \textbf{data\_6.pdf} to visualize the network. The larger the edge is, the bigger the capacity.

For this particular network, compute the minimum cut and report how you partitioned the vertices. To help you, the maximum flow has a value of 173.

\item Write the max-flow min-cut algorithm. It should be able to take in input a file formatted in the same way as described the previous part. To help you, We have provided a bigger network, called \textbf{data\_250.txt}, for which the maximum flow is 165.

You are asked to do your own implementation of the algorithm. You can use a graph library if you wish so, but this is not mandatory. Furthermore, we advise the students who have never used a graph library to not seek one, the time necessary to learn how it works will probably be substantially higher than the time to do this exercise. Of course, if you use a graph library, you are not supposed to just use \textbf{compute\_max\_flow()}!

You will be asked to compute the maximum flow of a unique network. Each student will have his own network. Please, contact the TA through Piazza (no personal e-mail) if you haven't received one by Thursday 1/17 evening.

\end{enumerate}

\end{enumerate}

\end{document}