%-*- 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{Oct 29, 2008}
    \duedate{Nov 12, 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{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}


\section{Even More Matchings}
\label{sec:even-more-matchings}

Continuing problem 5 from the midterm, our goal here is to design an even
faster algorithm for computing a maximum matching in a bipartite
graph. Note that the scheme we discussed in class runs in time $O(mn)$. 

Assume the existence of two procedures:
\begin{enumerate}
\item A procedure that in time $O(m)$ produces an augmenting path with
  respect to the current matching.
\item A procedure that takes a parameter $l$, and in time $O(m)$ returns a
  maximal vertex-disjoint set of augmenting paths of length $l$. You can
  further assume (it's actually true!) that there are no other augmenting
  path of length $l$.
\end{enumerate}

Consider the following algorithm:
\begin{enumerate}
\item Set $M = \emptyset$
\item For $i = 1 \ldots \sqrt{n}$
\item \ \ \ \ Find a maximal vertex-disjoint set of augmenting paths of length
  $i$, and augment $M$ with all these paths.
\item While any augmenting path remains
\item \ \ \ \ Augment $M$ with this path
\end{enumerate}

It's clear that the \texttt{for} loop runs in time $O(m\sqrt{n})$. Show
that after the loop completes, there are at most $\sqrt{n}$ augmenting paths
remaining (with arbitrary lengths), and therefore the entire algorithm
runs in time $O(m\sqrt{n})$. 


\end{document}


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