\documentclass{article}
\usepackage{graphicx,fancyhdr,amsmath,amssymb,amsthm,subfig,url,hyperref}
\usepackage[margin=1in]{geometry}

%----------------------- Macros and Definitions --------------------------

%%% FILL THIS OUT
\newcommand{\studentname}{Dan Guo}
\newcommand{\suid}{dguo1113}
\newcommand{\exerciseset}{CS221 Fall 2015 Homework 1}
%%% END



\renewcommand{\theenumi}{\bf \Alph{enumi}}

%\theoremstyle{plain}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}[theorem]{Lemma}

\fancypagestyle{plain}{}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[RO,LE]{\sffamily\bfseries\large Stanford University}
\fancyhead[LO,RE]{\sffamily\bfseries\large CS 261 Optimization and Algorithmic Paradigms}
\fancyfoot[LO,RE]{\sffamily\bfseries\large \studentname: \suid @stanford.edu}
\fancyfoot[RO,LE]{\sffamily\bfseries\thepage}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}

\graphicspath{{figures/}}

%-------------------------------- Title ----------------------------------

\title{CS261 \exerciseset}
\author{\studentname \qquad SUNet ID: \suid}

%--------------------------------- Text ----------------------------------

\begin{document}
\maketitle

\section*{Problem 1}

We will show a greedy algorithm for computing such decomposition. The correctness of the algorithm for an arbitrary flow will prove that every flow admits a decomposition of (P1) and (P2). Finally, we will show that the algorithm's running time is $O(mn)$ time.

\begin{enumerate}


\item Algorithm

\begin{enumerate}
  \item Part 1: While exist s-t path such that $f_e > 0, \forall e \in p$:
    \begin{enumerate}
      \item Pick one path p in flow $f$
      \item Let $\Delta = \min_{e \in p}\{f_e\}$
      \item Let ${f_e := f_e - \Delta} , \forall e \in p$
    \end{enumerate}
  \item Part 2: While exist $e \in E$ such that $f_e > 0$:
    \begin{enumerate}
      \item Take edges with positive flow until we reach a node we have visited before. (This builds a cycle $C$).
      \item Let $\Delta = \min_{e \in C}\{f_e\}$
      \item Let ${f_e := f_e - \Delta} , \forall e \in C$
    \end{enumerate}
\end{enumerate}

\item Correctness of Algorithm

\underline{Invariant INV}: $f$ is a flow.

\underline{Initialization}: We start with a flow $f$ so INV holds.

\underline{Iteration}: In an interation of Part 1, we decrease the flow through a path by the minimum flow in all edges of the path. Because we are only decreasing flow on the edges, capacity constraint holds. $\forall v \neq s, t$ in the path there is exactly an edge $(u,v)$ and edge $(v,w)$ where we both decrease flow on by $\Delta$. Thus conservation constraint holds. In an iteration of Part 2, we decrease the flow through a cycle by the minimum flow in all edges of the path. Because we are only decreasing flow on the edges, capacity constraint holds. $\forall v \in$ cycle $C$ is exactly an edge $(u,v)$ and edge $(v,w)$ where we both decrease flow on by $\Delta$. Thus conservation constraint holds.

Next we need to show that after Part 1, there will be no more s-t paths of positive flow. Because this algorithm strictly decreases flow on edges, a new edge with flow will not appear, only disappear, implying if we have no more s-t paths in a given iteration, there will be no more s-t paths in future iterations. Thus after Part 1, there will be no more s-t paths. 

\underline{Termination}: Each iteration we decrease flow by at least 1 unit, and as our starting flow $f$ is finite, this algorithm must terminate. 

(P1) By construction, at termination, there are no s-t paths and cycles with positive flow. If there were an edge with positive flow, it would not be part of an s-t path or cycle, so the conservation constraint would be violated at a given vertice. Thus all edges have zero flow. For every edge, its flow is distributed into paths by Part 1 and into cycles by Part 2. Thus, all flow is accounted for in every edge, by paths and cycles that run through it.

(P2) There will be as many paths and cycles as iterations of Part 1 and iterations of Part 2, as each Part creates a single path or cycle. Note that at each iteration, at least one edge is completely drained of flow, and hence will not participate in further path or cycle creation. As there are at most $m$ edges with flow in $f$, and each iteration decreases the number of edges with flow, we will only have at most $m$ iterations of Part 1 and Part 2, hence at most $m$ paths and cycles.

The algorithm is correct, and running this algorithm on an arbitrary flow implies that every flow admits a decomposition of (P1) and (P2).

\item %C
Part 1 can run at most m iterations as each iteration completely unsaturates an edge. After $m$ iterations, all edges are unsaturated, which means no s-t path exists. Thus, Part 1 runs $O(m)$ times. Picking an s-t path by DFS, finding the minimum flow on an s-t path, and decreasing flow on an s-t path are $O(n)$  as an s-t path is at most $n-1$ nodes in length. Thus Part 1 is$O(mn)$ time. 

Part 2 can run at most m iterations as each iteration completely unsaturates an edge. After $m$ iterations, all edges are unsaturated, which means no cycle exists. In an iteration, finding a cycle of positive flow from an edge by DFS, finding the minimum flow on the cycle, and decreasing flow on the cycle requires $O(n)$ time, as a cycle is at most n - 1 length.

\end{enumerate}

\section*{Problem 2}
\begin{enumerate}
\item Running Time

Initialize takes $O(m)$ time to initialize flow variables.

Retreat can occur at most $n$ times. If there are more than $n$ retreats, then at least $n$ vertices are removed, which cannot occur as $s,t$ cannot be removed by the algorithm. Thus, retreat is called at most $n$ times. Deleting a vertex and all its edges is $O(n)$ time as there is at most 1 edge between two vertices in the layered graph $L_f$, and there are at most $n$ vertices. Thus total time for retreat is $O(n^2)$.

Augment can occur at most $m$ times. Each augment call saturates and deletes an edge, and the graph has at most $m$ edges. Because an s-t path in layered graph $L_f$ is at most n-1 nodes, the time for finding smallest capacity on such path, augmenting flow on the path, and deleting edges on the path will be $O(n)$ in time. Total time for Augment is $O(mn)$.

There can be no more than $n$ advance calls between an Augment, because Advance is creating a path from a vertex to t in the layered graph (thus no cycles or sideways edges), and an s-t path is at most $n - 1$ edges in length. The time in an Advance call is constant, since we are simply appending an edge. Thus the time for Advance between two Augment calls is $O(n)$. As there are at most $m$ augment calls, the total tiem for Advance is $O(mn)$.

In total, the sum time of all operations is $O(mn)$.


\item 
From part (a), as the number of operations in the algorithm is bounded, the algorithm will terminate. 

Next we show the algorithm terminates with a blocking flow. Assume for sake of contradiction that the algorithm terminates without a blocking flow. This means that there exists an s-t path in $L_f$. Termination occurs when Retreat is called in Advance call, and $s$ is the endpoint of path $P$. Note that for Retreat to be called, there must be no edges out of the endpoint of path $P$, or edges out of $s$. This contradicts the existence of an s-t path in $L_f$, as such a path requires an edge out of $s$. Thus our assumption was wrong, the algorithm terminates with a blocking flow.

\item Running Time in 1-unit capacity graph

Initialize takes $O(m)$ time to initialize flow variables.

Retreat can occur at most $n$ times. If there are more than $n$ retreats, then at least $n$ vertices are removed, which cannot occur as $s,t$ cannot be removed by the algorithm. Thus, retreat is called at most $n$ times. Deleting a vertex and all its edges is $O(1)$ time, in the case where we use an adjacency list method of storage. Thus retreat is $O(n)$ time. TODO make sure correct.

Augment can occur at most $m$ times. Each augment call saturates and deletes an edge, and the graph has at most $m$ edges. Because an s-t path in layered graph $L_f$ is at most n-1 nodes, the time for finding smallest capacity on such path, augment flow on the path, and deleting edges on the path will be $O(n)$ in time. Total time for Augment is $O(mn)$. TODO how we got it down to $O(m)$.

Advance considers an edge on path $P$ and eventually saturates/deletes the edge (in Augment) or deletes it (in Retreat). Thus, there can be at most $m$ Advance calls. The time in an Advance call is constant, since we are simply appending an edge. Thus total time in Advance is $O(m)$.

In total, the sum time of all operations is $O(m)$.


\end{enumerate}

\section*{Problem 3}
\begin{enumerate}
\item 

\item %B

\item Runtime

In (1), creation of heap is $O(nlogn)$. (2) is $O(n)$ as topological sort is linear in the number of vertices. (3) is $O(m)$ time, visiting each edge once. We will show that (4) takes at most $O(n^2logn)$ time, which shows that the algorithm runs in $O(n^2logn)$ time.

In (4), 


\item %D

\item %E

\end{enumerate}


\end{document}
