%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{color}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{tikz}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}

\newcommand{\ignore}[1]{}

\begin{document}
% Do not modify 


%Do not modify
\begin{textblock*}{16cm}(-1.7cm,-2.3cm)
\noindent {\large CS 580-Spring 2019} \\
\noindent {\large Instructor: Jeremiah Blocki} \\
\noindent {\large TAs:  Hamidreza Amini Khorasgani, Akash Kumar} \\
\noindent {\large I collaborated with (...). I affirm that I wrote the solutions in my own words and that I understand the solutions I am submitting.}
\end{textblock*}

%Do not modify other than putting your name where stated
\begin{textblock*}{8cm}(12.5cm,-1cm)
%\noindent {Name: } 
\end{textblock*}
%Do not modify other than typing your acknowledgement where stated
\begin{textblock*}{13.5cm}(-1.7cm,-1.8cm)
\noindent \textit{\footnotesize  } 
\end{textblock*}

\vspace{1cm}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 4} \\ 
\textbf{Due Date: March 8, 2019 at 11:59PM on Gradescope.}%\\
%\textbf{Instructor: Jeremiah Blocki}\\
%\textbf{TAs: Chang Li, Akash Kumar}
\end{center}

\subsection*{Question 1}
\begin{enumerate}
\item Use Dinic's algorithm to compute the maximum flow of the graph below. You should show the level graph/blocking flow after every step of the algorithm. If you find that it saves time you may scan handwritten pictures.  (Alternatively, you may also copy-paste the LaTeX source for the graph below)
\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[
roundnode/.style={circle, draw=black!60, very thick, minimum size=7mm}]
%Nodes
\node[roundnode] (s) at (1,0) {$s$};
\node[roundnode] (V2) at (4,0) {$b$};
\node[roundnode] (V3) at (7,0) {$c$};
\node[roundnode] (t) at (13,0) {$t$};
\node[roundnode] (V4) at (5.5,3) {$a$};
\node[roundnode] (V5) at (5.5,-3) {$d$};
\node[roundnode] (V6) at (10,3) {$f$};
\node[roundnode] (V7) at (10,-3) {$g$};

%Lines
\draw[->] (s.east) -> (V2.west) node[pos=0.5,above]{3};
\draw[->] (V2.east) -> (V3.west) node[pos=0.5,above]{6};
\draw[->] (V3.east) -> (t.west) node[pos=0.4,above]{5};
\draw[->] (s) -> (V4) node[pos=0.5,left, outer sep=2pt]{10};
\draw[->] (V4) -> (V2) node[pos=0.7,right]{1};
\draw[->] (V4) -> (V3) node[pos=0.5,right, outer sep=2pt]{2};
\draw[->] (V4) -> (t) node[pos=0.4,above]{5};
\draw[->] (s) -> (V5) node[pos=0.4,below]{1};
\draw[->] (V5) -> (V2) node[pos=0.6,right]{2};
\draw[->] (V5) -> (V3) node[pos=0.5,right]{2};
\draw[->] (V6) -> (t) node[pos=0.5,right]{8};
\draw[->] (V5) -> (t) node[pos=0.25,below]{6};
\draw[->] (V7) -> (t) node[pos=0.5,right]{2};
\draw[->] (V7) -> (V6) node[pos=0.1,right]{3};
\draw[->] (V3) -> (V7) node[pos=0.3,right]{5};
\draw[->] (V4) -> (V6) node[pos=0.5,above]{4};
% \draw (V1.east) -- (V2.west) node[pos=0.5,above,fill=white]{1};
% \draw (V3.east) -- (V4.west) node[pos=0.5,below,fill=white]{2};
% \draw (V2.south west) -- (V3.north east) node[pos=0.5,left]{3};
\end{tikzpicture}
\caption{Flow Network}
\label{fig:p1}
\end{figure}

% Some of the ignored LaTex code below might be helpful if you want to draw residual graphs in LaTex directly.
\ignore{
\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[
roundnode/.style={circle, draw=black!60, very thick, minimum size=7mm}]
%Nodes
\node[roundnode] (s) at (1,0) {$s$};
\node[roundnode] (V2) at (4,0) {$b$};
\node[roundnode] (V3) at (7,0) {$c$};
\node[roundnode] (t) at (10,0) {$t$};
\node[roundnode] (V4) at (5.5,3) {$a$};
\node[roundnode] (V5) at (5.5,-3) {$d$};


%Lines
\draw[->] (s.east) -> (V2.west) node[pos=0.5,above]{3} node[rectangle,draw, outer sep=2pt, pos=0.5,below]{3};
\draw[->] (V2.east) -> (V3.west) node[pos=0.5,above]{6} node[rectangle,draw, outer sep=2pt, pos=0.5,below]{5};
\draw[->] (V3.east) -> (t.west) node[pos=0.4,above]{5} node[rectangle,draw, outer sep=2pt, pos=0.4,below]{5};
\draw[->] (s) -> (V4) node[pos=0.5,left, outer sep=2pt]{10} node[rectangle,draw, outer sep=14pt, pos=0.7,left]{4};
\draw[->] (V4) -> (V2) node[pos=0.7,right]{1} node[rectangle,draw, outer sep=6pt, pos=0.5,right]{1};
\draw[->] (V4) -> (V3) node[pos=0.5,right, outer sep=2pt]{2};
\draw[->] (V4) -> (t) node[pos=0.4,above]{5} node[rectangle,draw, outer sep=14pt, pos=0.5,right]{3};
\draw[->] (s) -> (V5) node[pos=0.4,below]{1} node[rectangle,draw,outer sep=6pt, pos=0.5,below]{1};
\draw[->] (V5) -> (V2) node[pos=0.6,right]{3} node[rectangle,draw,outer sep=6pt, pos=0.6,left]{1};
\draw[->] (V5) -> (V3) node[pos=0.5,right]{3};
\draw[->] (V5) -> (t) node[pos=0.5,right]{10};

% \draw (V1.east) -- (V2.west) node[pos=0.5,above,fill=white]{1};
% \draw (V3.east) -- (V4.west) node[pos=0.5,below,fill=white]{2};
% \draw (V2.south west) -- (V3.north east) node[pos=0.5,left]{3};
\end{tikzpicture}
\caption{Question 9 Flow Network}
\label{fig:p1}
\end{figure}}


\item What is the minimum capacity $s$-$t$ cut for the above flow network?

\end{enumerate}

\subsection*{Question 2}
\begin{enumerate}
\item Suppose we are given a bipartite graph $G = (V=(L,R),E)$ where the left nodes $L=\{u_1,\ldots,u_n\}$ and the right nodes are $R=\{v_1,\ldots,v_n\}$ we want to determine whether or not a perfect matching $M^* \subseteq E$ exists with $|M^*|= n$.  Further suppose that $G$ contains the edge $\{u_i,v_i\} \in E$ for each $i \leq n - \log n$, but for $i > n-\log n$ it may or may not be the case that $\{u_i,v_i\} \in E$. Develop an $O(|E| \log n)$ time algorithm to determine whether or not a perfect matching exists and explain why your algorithm is correct. 
\item Suppose that $G$ does not have a perfect matching. Extend your algorithm from the previous part to produce a short certificate $C$ with $|C| = O(n)$ which proves that $G$ does not have a perfect matching. You should also develop a linear time algorithm $\mathcal{A}$ which validates the certificate in time $O(|E|+n)$. You should prove that $\mathcal{A}(C,G)$ always accepts honestly produced certificates (those output by your algorithm), but that if $G$ does have a perfect matching then for {\em any} certificate $C$  $\mathcal{A}(C,G)$ always rejects.   
\end{enumerate}

\subsection*{Question 3 (Network flow with taxation)} 
%Write down a linear program to solve the following problems. In each case you should explain why your linear program is correct. Your explanation should include a clear description of each variable and each constraint.
Recall that in the standard network flow problem we required that the for each vertex $v$ (excluding the source $s$ and sink $t$) the sum of the flow into that vertex is equal to the sum of flow out of that vertex. Suppose that we replace this {\em conservation constraint} with a {\em taxation constraint}. In particular, suppose each vertex represents a country and that each country $v \notin \{s,t\}$  has an associated tax-rate $0 < t_v < 1$ meaning that country $v$ will keep $t_v$ fraction of the goods flowing through node $v$. Given a flow network $G=(V,E)$ with maximum capacities $c(e)$ on each edge $e \in V$ and tax rates $t_v$ for each node $v \notin \{s,t\}$ our goal is to find the maximum amount of goods that can be transported from $s$ to $t$ under these taxation constraints. Write down a LP to solve this problem. You should explain why your linear program is correct. (Note: A good explanation will always include a clear/intuitive description of each variable and each constraint.)



% Good practice question below, but you don't need to answer it
\ignore{
\subsection*{Question 2} 
In two-player zero-sum game we are given a $n_1 \times n_2$ payoff matrix $M \in \mathbb{R}^{n_1 \times n_2}$ along with a list of $n_1$ actions (resp. $n_2$ actions) that player 1 (resp. player 2) might take. If player $1$ takes action $a_i \leq n_1$ and player $2$ plays action $a_j \leq n_2$ then player $1$ receives reward $M[a_i,a_j]$ and player $2$ receives reward $-M[a_i,a_j]$ --- note that the sum of rewards is $0$. Both players must select an action simultaneously and without knowledge of the action that the other player takes. Rock-Paper-Scissors is a classic examples of a zero-sum game e.g., with rewards $M[paper,rock] = 1 = -M[rock,paper]$ (paper beats rock),   $M[rock,scissors] = 1 = M[scissors,rock] $ (rock beats scissors), $M[scissors,paper] = 1 = M[paper, scissors] $ (scissors beats paper) and $M[rock,rock]=0 = M[scissors,scissors] = M[paper,paper]$ (e.g., rock ties rock). In many zero-sum games the optimal strategy is to play a randomized strategy (also called a mixed strategy) e.g., if player 2 knows that player 1 always plays `paper' then player 2 will choose to play `scissors.'   In general, a mixed strategy for player 1 (resp. player 2) is a probability distribution $\vec{p}= p_1,\ldots, p_{n_1}$ (resp. $\vec{q}=q_1,\ldots, q_{n_1}$) over the $n_1$ actions of player $1$ (resp. $n_2$ actions of player 2). Note that if player $1$ plays mixed strategy $\vec{p}$  and player $b$ plays action $j \leq n_2$ then the expected reward for player 1 is
\[ \sum_{i=1}^{n_1} p_i M[i,j]  \ .\]
We say that the value of a mixed strategy $\vec{p}$ for player 1 is 
\[V_1(\vec{p})= \min_{j\leq n_2} \left\{\sum_{i=1}^{n_1} p_i M[i,j]  \right\} \ . \]
Similarly, the value of mixed strategy 
 $\vec{q}$ for player 2 is 
\[V_2(\vec{q})= \min_{i\leq n_1} \left\{ - \sum_{j=1}^{n_2} q_j M[i,j]  \right\} \ . \]
The value of the game $V_1^*$ (resp. $V_2^*$) for player 1 (resp. player 2) is the value of the best mixed strategy i.e., $V_1^* = \max_{ \vec{p}} V_1(\vec{p})$ and $V_2^* = \max_{ \vec{q}} V_1(\vec{q})$.  
\begin{enumerate}
\item Consider the mixed strategy $\vec{p} =p_{rock} = 0,p_{scissors} = \frac{1}{2}$ and $p_{paper}=\frac{1}{2}$ for player 1 in Rock-Paper-Scissors. What is the value of this mixed strategy?
\item Prove that $V_1^* = - V_2^*$. 
\item Let $\vec{p}^*$ and $\vec{q}^*$ be given s.t. $V_1^* = V_1(\vec{p}^*)$ and $V_2^* = V_2(\vec{p}^*)$. Prove that the pair of mixed strategies $\vec{p}^*$ and $\vec{q}^*$ are stable in the sense that for all alternative player 1 strategies $\vec{p}$ we have 
\[ \sum_{i=1}^{n_1} \sum_{j=1}^{n_2} p_i q_j^* M[i,j] \leq \sum_{i=1}^{n_1} \sum_{j=1}^{n_2} p_i^* q_j^* M[i,j] \ ,\]
and similarly
for all $\vec{q}$ we have 
 \[ \sum_{i=1}^{n_1} \sum_{j=1}^{n_2} p_i^* q_j (-M[i,j]) \leq \sum_{i=1}^{n_1} \sum_{j=1}^{n_2} p_i^* q_j^* (-M[i,j]) \ .\]
\end{enumerate}

}
%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.
\subsection*{Question 4} 

Suppose that we order the edge relaxations in each pass 
of the Bellman-Ford algorithm as follows. Before the 
first pass, we assign an arbitrary linear order $v_1, v_2, \dots, v_{|V|}$ to the vertices of the input graph 
$G=(V,E)$. Then, we partition the edge set $E$ into 
$E_f\cup E_b$, where $E_f=\{(v_i,v_j)\in E :i < j\}$ and 
$E_b=\{(v_i,v_j) \in E : i > j\}$. (Assume that $G$ contains 
no self-loops, so that every edge is in either $E_b$ or 
$E_f$). Define $G_f=(V,E_f)$ and $G_b=(V,E_b)$.

\begin{itemize}
    \item Prove that $G_f$ is acyclic with topological 
    sort $\langle v_1, v_2, \dots, v_{|V|} \rangle$ and that $G_b$ is
    acyclic with topological order $\langle v_{|V|}, v_{|V|-1},
    \dots, v_1 \rangle$.\\
    
    \item Suppose that we implement each pass of the 
    Bellman-Ford algorithm in the following way. We visit
    each vertex in the order $v_1, v_2, \dots, v_{|V|}$ 
    relaxing edges of $E_f$ that
    leave the vertex. We then 
    visit each vertex in the order $v_{|V|}, v_{|V|-1},
    \dots, v_1$ relaxing edges of 
    $E_b$ that leave the vertex.
    \item Prove that with this scheme, if $G$ contains no
    negative-weight cycles that are reachable from the 
    source vertex $s$, then after only $\lceil 
    |V|/2\rceil$ passes over the edges, $v.d=\delta(s,v)$
    for all vertices $v\in V$. (Here, $\delta(s,v)$ represents the length of the shortest path from $s$ to $v$ and $v.d$ represents the distance we have computed in the algorithm. )\\
    
    \item Does this scheme improve the asymptotic running
    time of the Bellman-Ford algorithm?
\end{itemize}


\subsection*{(Bonus) 10 points}
A set of positive integers 
$P=\{a_1,a_2,\dots,a_n\}$ is given. 
Give an algorithm which outputs two 
subsets of $P$, $S_1$ and $S_2$
such that $S_1\cup S_2=P$ and $S_1\cap 
S_2=\emptyset$ and
$d:=\left|\sum_{a_i\in S_1}a_i-\sum_{a_j\in S_2}a_j\right|$ is 
minimum (If $S=\emptyset$, we define $\sum_{a_i\in 
S}a_i=0$). Your algorithm should run in time
$O(nM)$ where $M = \sum_{i=1}^n a_i$ represents the 
summation of all numbers in the set $P$.
\end{document}