% Instructions: you don't need to change anything in the macros, but
% feel free to define new commands as you wish. Starting from the main
% body, change the specs (e.g., your
% name). use \begin{solution} \end{solution} environment to write your
% solutions. Don't forget to list your collaborators.

\documentclass[12pt,addpoints,answers]{exam}
%============Macros==================%
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage[margin=1in]{geometry}
%--------------Cosmetic----------------%
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{microtype}
\usepackage{xspace}
\usepackage[svgnames]{xcolor}
\usepackage[sc]{mathpazo}
\usepackage{enumitem}
\setlist[enumerate]{itemsep=1pt,topsep=2pt}
\setlist[itemize]{itemsep=1pt,topsep=2pt}
%----------Header--------------------%
\def\course{CSCE629 Analysis of Algorithms}
\def\term{Texas A\&M U, Fall 2019}
\def\prof{Lecturer: Fang Song}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{\arabic{page}}
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { \hfill \large{\course} \hfill }
       \vspace{2mm}
       \hbox to 5.78in { {\Large \hfill \textbf{#5}  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { \term \hfill \emph{#2}}
       \hbox to 5.78in { {#3 \hfill \emph{#4}}}
      }
   }
   \end{center}
   \vspace*{4mm}
}
\newcommand{\hw}[4]{\handout{#1}{#2}{#3}{#4}{Homework #1}}

%-----defs and commands-----%
%\def\mG{[\textbf{G}]\xspace}
\def\veps{\varepsilon}
\newcommand{\bit}{\{0,1\}}
\newcommand{\negl}{\text{negl}}
\newcommand{\corr}[1]{{\color{blue}{#1}}}
\newcommand{\alg}[1]{\textsf{#1}}
%=======Main document==============%
\begin{document}

%----Specs: change accordingly-----%
\newif\ifstudent % comment out false
\studenttrue 
% \studentfalse

\def\hwnum{8}
\def\issuedate{10/25/19}
\def\duedate{10am, 11/01/19} % 
\def\yourname{your name} % put your name here
%------------------------------%

\ifstudent
\hw{\hwnum}{\issuedate}{Student: \yourname}{Due: \duedate}%
\else
\hw{\hwnum}{\issuedate}{\prof}{Due: \duedate}%
\fi

\noindent \textbf{Instructions.}

\begin{itemize} 
\item Typeset your submission by \LaTeX, and submit in PDF
  format. Your solutions will be graded on \emph{correctness} and
  \emph{clarity}. You should only submit work that you believe to be
  correct, and you will get significantly more partial credit if you
  clearly identify the gap(s) in your solution. You may opt for the
  ``I’ll take 15\%'' option.
\item You may collaborate with others on this problem set.  However,
  you must \textbf{{write up your own solutions}} and \textbf{{list
      your collaborators and any external sources}} for each
  problem. Be ready to explain your solutions orally to a course staff
  if asked.
\item For problems that require you to provide an algorithm, you must
  give a precise description of the algorithm, together with a proof
  of correctness and an analysis of its running time. You may use
  algorithms from class as subroutines. You may also use any facts
  that we proved in class or from the book.
\item \textbf{If you describe a Greedy algorithm, you will get no
    credit without a formal proof of correctness, even if your
    algorithm is correct.}
\end{itemize}

\noindent This assignment contains \numquestions\ questions,
\numpages\ pages for the total of \numpoints \ points and
\numbonuspoints\ bonus points. A random subset of the problems will be
graded. \medskip

\paragraph{Exercises. Do not turn in.}
\begin{questions}
\question Let $f$ and $f'$ be feasible $(s,t)$-flows in a flow network
  $G$, such that $v(f') > v(f)$. Prove that there is a feasible
  $(s,t)$-flow with value $v(f') - v(f)$ in the residual network
  $G_f$.

\question Let $u\to v$ be an arbitrary edge in an arbitrary flow
  network $G$. Prove that if there is a minimum $(s,t)$-cut $(S,T)$
  such that $u\in S$ and $v\in T$, then there is \emph{no} minimum cut
  $(S',T')$ such that $u\in T'$ and $v\in S'$. 
\end{questions}
\newpage 
\paragraph{Problems to turn in.}

\begin{questions}

\question[10] (Stabbing points) Let $X$ be a set of $n$ intervals on
  the real line. We say that a set $P$ of points \emph{stabs} $X$ if
  every interval in $X$ contains at least one point in $P$. Describe
  and analyze an efficient algorithm to compute the smallest set of
  points that stabs $X$. Assume that your input consists of two arrays
  $L[1,\ldots,n]$ and $R[1,\ldots,n]$, representing the left and right
  endpoints of the intervals in $X$. (N.B. If you use a greedy
  algorithm, you must prove its correctness.)
  \newpage

\question[10] (Maximum spanning tree) Describe and analyze an algorithm to
  compute the \emph{maximum}-weight spanning tree of a given
  edge-weighted graph. 

  \newpage
  

\question (Demand) Suppose instead of capacities, we consider networks
  where each edge $u\to v$ has a non-negative \emph{demand}
  $d(u\to v)$. Now an $(s,t)$-flow $f$ is \emph{feasible} if and only
  if $f(u\to v)\ge d(u\to v)$ for every edge $u\to v$. (Feasible flow
  values can now be arbitrarily large.) A natural problem in this
  setting is to find a feasible $(s,t)$-flow of \emph{minimum} value.

  \begin{parts}
  \part[10] Describe an efficient algorithm to compute a feasible
    $(s,t)$-flow, given the graph, the demand function, and vertices
    $s$ and $t$ as input. (Hint: find a flow that is non-zero
    everywhere, and then scale it up to make it feasible.)
  \part[10] Suppose you have access to a subroutine \alg{MaxFlow} that
    computes \emph{maximum} flows in networks with edge
    capacities. Describe an efficient algorithm to compute a
    \emph{minimum} flow in a given network with edge demands; your
    algorithm should call \alg{MaxFlow} exactly once.

  \part[10] State and prove an analogue of the max-flow min-cut theorem
    for this setting. (Do minimum flows correspond to maximum cuts?)
  \end{parts}

\end{questions}
\end{document}
