%-*- LaTeX -*-

\NeedsTeXFormat{LaTeX2e}
\documentclass{assign}
\usepackage{newcent}
\usepackage{amsmath,amssymb,enumitem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Start reading here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The four commands below are used to define the ordinal number of the
% lecture (can be found on the lecture syllabus), the title of the lecture
% (formulate the best description you can come up with; you can always
% resort to the tentative title on the lecture syllabus if you have
% difficulty), the date of the lecture (in this format: DD Month YYYY),
% and the name of the scribe (that's you).
%
% Please supply correct arguments for the four commands below:
%

    \lecturenumber{4}
    \lecturetitle{Homework\ }
    \lecturedate{Nov 12, 2007}
    \duedate{Nov 21, 2007}
    \lecturescribe{}

%
% In the space indicated below, please type out your lecture notes.  You
% should use all the standard LaTeX typesetting conventions, plus a couple
% of additional commands described below.  If you are unfamiliar with using
% LaTeX to typeset technical documents, please read the very useful summary
% entitled ``The Not So Short Introduction to LaTeX2e'' which is available
% on BlackBoard.  You can also examine the source files for the scribed
% lecture notes from lectures 1, 2, and 3 for some formatting ideas. 
%
% Use the standard commands \section{}, \subsection{}, and \subsubsection{}
% to format your document logically into sections, subsections, and 
% subsubsections (as needed). 
%
% If you reference a URL anywhere, use the provided command \urlclick{}
% like this: \urlclick{http://www.web.com/foo.html}.  This will create a
% clickable hyperlink in the resulting .pdf file. 
%
% To add a figure to your notes, use the provided command \figureadd{}
% like this: \figureadd{basename}{label}{caption}.  In this command,
% basename is the base name of your figure, which must exist in both .eps
% and .jpg formats.  For example, if you have created a figure named both
% foo.jpg and foo.eps, then the basename is simply foo.  The label field
% creates a label which you can reference elsewhere using the standard
% command \ref{}.  Please use the caption field to provide a descriptive
% caption for any figure you create.  When you submit your scribed notes,
% please also submit all your figure files in both .eps and .jpg formats.
%
% For a theorem, corollary, lemma, claim, fact, definition, assumption,
% observation, or example, consider using these provided commands to set it
% apart from other text: 
%     \theorem{...}
%     \corollary{...} 
%     \lemma{...}
%     \claim{...}
%       etc.
%
% For proofs, or sketches of proofs, use these provided environments: 
%     \begin{proof}        ... \end{proof}
%     \begin{proof_sketch} ... \end{proof_sketch}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\reals}{{\mathbb R}}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\ch}{\ensuremath\mathcal{CH}}
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{lemma}{Lemma}[section]
% \newtheorem{corollary}{Corollary}[section]
% \newtheorem{claim}{Claim}[section]
% \newtheorem{prop}{Proposition}[section]
% \newtheorem{fact}{Fact}[section]
% \newtheorem{problem}{Problem}[section]
% \numberwithin{equation}{section}
\newtheorem{defn}{Definition}[section]
\newenvironment{proofsketch}{\par{\textbf{Proof Sketch:}}}{\(\qed\) \par}

\begin{document}
\label{begin}


\section{Simulating A Flow}
\label{sec:simulating-flow}

Consider the following network (numbers on edges are capacities):
\begin{figure}[ht]
  \centering
  \includegraphics[width=2in]{graph}
\end{figure}
\begin{enumerate}[label=\alph*)]
\item Simulate the Ford-Fulkerson algorithm and find the max flow and min
  cut. Show the working of the algorithm by showing each augmenting path.
\item Draw the residual graph obtained after the algorithm is
  complete. Mark all vertices reachable from S, and those that can reach
  T. You may omit edges with zero capacity.
\item An edge in the network is called a \emph{bottleneck} edge if
  increasing its capacity will increase the max flow. Mark all bottleneck
  edges in the network.
\item Give an example of a network with no bottleneck edges (!).
\item Give an efficient algorithm to find all bottleneck edges in a
  network (Hint: compute a max flow, and then look at the residual graph)
\end{enumerate}


\section{Updating A Flow}
\label{sec:updating-flow}

\begin{enumerate}[label=\alph*)]
\item An edge of a flow network is called \emph{critical} if decreasing
  the capacity of that edge decreases the max flow. Give an efficient
  algorithm to find a critical edge in a network
\item Suppose we reduce by one unit the capacity of an edge on which the flow equalled
  the capacity. We can run the max flow algorithm again to find the new
  flow; however, we can do better. Assume that all capacities and flow are
  integral, and give an algorithm running in time $O(|V| + |E|)$ that
  updates the flow. 
\end{enumerate}


\section{Vertex Covers}
\label{sec:vertex-covers}

\begin{enumerate}[label=\alph*)]
\item Show that we can compute the minimum vertex cover of a \emph{bipartite
  graph} using a max flow computation.
\item \textsc{vertex cover} is NP-Complete. Why does the above not show
  that P = NP ? 
\end{enumerate}


\section{Problem 7.6 from KT}
\label{sec:problem-7.6-from}



\section{Problem 7.17 from KT}
\label{sec:problem-7.17-from}


\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: