\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage[dvipsnames]{xcolor}
\usepackage{graphicx,fancyhdr,algorithm,algorithmic}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage{multicol}
\usepackage{enumitem} 
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{arrows,automata}
\usepackage{thmtools}


\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}

\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}

\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{ForestGreen!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=ForestGreen, backgroundcolor=ForestGreen!5,
    }
]{thmgreenbox}
\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{Red!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=Red, backgroundcolor=Red!5,
    }
]{thmredbox}
\declaretheorem[style=thmgreenbox, name=Hint,numbered=no]{hint}
\declaretheorem[style=thmredbox, name=Note,numbered=no]{warning}

\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS256:~Algorithm Design and Analysis \hfill #1} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #2 \normalsize{(#3)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #4 \hfill  } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}

\begin{document}
\homework{Spring 2024}{Assignment 6}{due 04/24/2024 at 9:59pm}{Sam McCauley}{}

\begin{warning}
	This assignment is to be done individually.
\end{warning}

\bigskip
\begin{question}(KT 7.5)
Are the following statements true or false?  If true, you must give a justification.; if false, you must give a counterexample.

\begin{enumerate}[label = (\alph*), noitemsep]

    \item Let $G$ be an arbitrary flow network, with a source $s$, a sink $t$, and a positive integer capacity $c_e$ on every edge $e$. If $f$ is a maximum $s-t$ flow in $G$, then $f$ saturates every edge out of $s$ with flow (i.e., for all edges $e$ out of $s$, we have $f(e) = c_e)$.

    \item 
    Let $G$ be an arbitrary flow network, with a source $s$, a sink $t$, and a positive integer capacity $c_e$ on every edge $e$. Let $(A, B)$ be a minimum $s$-$t$ cut with respect to the capacities $\{c_e : e \in E\}$.  Now suppose we add $1$ to every capacity; then $(A, B)$ is still a minimum $s$-$t$ cut with respect to the new capacities $\{1 + c_e : e \in e\}$.
\end{enumerate}

\begin{solution}

\end{solution}

\end{question}


\newpage
\begin{question} (Modified KT 7.23 and 7.24)
Suppose you’re looking at a flow network $G$ with source $s$ and sink $t$, and you want to be able to express
something like the following intuitive notion: {\em Some nodes are clearly on the ``source side'' of the main bottlenecks; some nodes are clearly on the ``sink side'' of the main bottlenecks; and some nodes are in the middle.} However, $G$ can have many minimum cuts, so we have to be careful in how we try making this idea precise. Here's one way to divide the nodes of G into three
categories of this sort.
\begin{itemize}[noitemsep]
    \item We say a node $v$ is {\em upstream} if, for all minimum $s$-$t$ cuts $(A, B)$, we have $v \in A$---that is, $v$ lies on the source side of every minimum cut.
    \item We say a node $v$ is {\em downstream} if, for all minimum $s$-$t$ cuts $(A, B)$, we have $v \in B$—that is, $v$ lies on the sink side of every minimum cut.
    \item We say a node $v$ is {\em central} if it is neither upstream nor downstream; there is at least one minimum $s$-$t$ cut $(A, B)$ for every $v \in A$, and at least one minimum $s$-$t$ cut $(A', B')$ for which $v \in B'$.
\end{itemize}
In this question, we design an algorithm to classify vertices of $G$ into these categories and use the classification to characterize graphs that have a unique minimum cut. Let $f$ be the maximum flow in $G$. Consider the cut $(A^*, B^*)$, where 
$A^* =\{u ~|~ u \mbox{ is reachable from $s$ in $G_f$}\}$ and 
let $B^* = V-A^*$.  Thus, $v(f) = cap(A^*,B^*)$ and $(A^*,B^*)$ is a minimum cut of $G$.
\begin{enumerate}[label = (\alph*), noitemsep]
    \item  Show that the set $A^*$ is the set of upstream vertices of $G$, that is, $v$ is upstream if and only if $v \in A^*$.

   \item Using part (a), describe an efficient algorithm to find the downstream vertices in $G$. (\emph{Hint.} Consider the graph $G^R$, with all direction of edges in $G$ reversed. $G^R$ now has source $t$ and sink $s$.)
   
   \item Show that $G$ has a unique minimum cut if and only if $G$ has no central vertices, that is, the union of upstream and downstream vertices is the set $V$.
\end{enumerate}
\end{question}

\begin{solution}

\end{solution}

\newpage
\begin{warning}
	This question is about network flow reductions.  We will begin those Thursday, but you'll see much more about them on Monday---you can probably start thinking about this problem before Monday's class, but you'll have an easier time solving it completely after the lecture.
\end{warning}

\begin{question} (From Dave Mount's Algorithms Class)
The computer science department at a major university has a tutoring program.
There are $m$ tutors, $\{t_1, \ldots, t_m\}$ and $n$ students who have requested the tutoring service
$\{s_1, \ldots , s_n\}$. Each tutor $t_i$ has a set $T_i$ of topics that they know, and each student $s_j$ has
a set of topics $S_j$ that they want help with. We say that tutor $t_i$
is suitable to work with
student $s_j$ if $S_j \subseteq T_i$ 
(That is, the tutor $t_i$ knows all the topics of interest to student $s_j$.) Finally, each tutor $t_i$ has a range $[a_i, b_i]$, indicating that $t_i$ would like to work with at least $a_i$ students (so 
their time is well-utilized) and at most $b_i$ students (so they are not overburdened).

Given a list of students, a list of tutors, the ranges $[a_i, b_i]$ for the tutors, and a list of suitable tutors for each student, describe an efficient algorithm that determines whether it is possible to generate a pairing of tutors to students such that:
\begin{itemize}[noitemsep]
    \item Each student is paired with exactly one tutor.
    \item Each tutor $t_i$ is paired with at least $a_i$ and at most $b_i$ students.
    \item Each student is paired only with a suitable tutor.
\end{itemize}
\end{question}



\begin{solution}

\end{solution}


\end{document}
