<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}



%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&amp;$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM
% HERE:


\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\problemset{4}{May 6}{\bf May 13}


Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}
\item Consider the problem of correcting typing errors that omit
  spaces; for example we would like to correct ``meetatone'' to
  ``meet at one'' and not ``me eta tone'' or many others
  decompositions that are less plausible. Assume that we have access to
  a quality function $q$ that returns a numerical score for each
  string. The quality of a decomposition of the string $x =
  x_1x_2\cdots x_n$ into $x = y_1y_2\cdots y_k$, where each $y_i$ is a
  string itself, is given by $\sum_{i=1}^k q(y_i)$.

Devise a dynamic programming algorithm that computes the highest
quality decomposition of $x$. Your algorithm should run in time
$O(n^3)$, counting evaluations of $q$ as unit cost operations.

\item Given a directed graph $G$ with positive edge weights,
  and two vertices $s$ and $t$, we would like to compute a measure of the ``robustness'' of the
  shortest path from $s$ to $t$, by computing the {\em number} of
  these shortest paths.

Devise a dynamic programming algorithm to
  compute the number of shortest $s$-$t$ paths in $G$, that runs in time
  $O(nm)$. You may count arithmetic operations as unit cost
  operations.

\item Let $E$ be a finite set and let ${\mathcal I}_1$ and ${\mathcal
    I}_2$ be matroids over $E$. The problem of finding a maximum {\em cardinality} independent set in
${\mathcal I}_1 \cap {\mathcal I}_2$ can be solved in polynomial time,
with polynomially many checks to determine if a specified subset is an
indepedent set in one of the two matroids.

Formulate the bipartite maximum matching problem as the problem
  of finding a maximum cardinality independent set in the intersection
  of two matroids.

\item In this problem you will prove two facts about the structure of perfect matchings in
  bipartite graphs.
\begin{enumerate}
\item A $k$-regular graph is one in which the degree of every vertex
  is $k$. Prove that every $k$-regular bipartite graph has a perfect
  matching by formulating the matching problem as a flow problem and
  studying the maximum flow.

\item A more general fact is known as Hall's Theorem. Let $G = (U \cup V, E)$ be a undirected
  bipartite graph, and for a subset $S \subseteq U$, let $N(S)$ denote
  the neighbors of the vertices in subset $S$.

Prove that there exists
  a perfect matching in $G$ if and only if we have $|N(S)| \ge |S|$ for
  all subsets $S \subseteq U$. Hint: for one direction,
  formulate the matching problem as a flow problem, and use the
  min-cut to identify a subset $S$ for which $|N(S)| &lt; |S|$.
\end{enumerate}

\item Extensions to max-flow and an application. Given a directed graph $G = (V, E)$, non-negative
  integer capacities $c(e)$ for
  each edge $e \in E$, and integer {\em demands} $d(v)$ for each
  vertex, a {\em circulation} is a function $f$ satisfying
\begin{itemize}
\item  $0 \le f(e) \le c(e)$ for all $e \in E$, and
\item for all $v \in V$, \[\sum_{e \mbox{ entering } v}f(e) - \sum_{e \mbox{ exiting }
    v}f(e) = d(v).\]
\end{itemize}
\begin{enumerate}
\item Show how to find a circulation, or determine that one does not exist, by reducing to
max-flow. Your algorithm should run in time comparable to the
algorithms for max-flow on graphs with size parameters $n = |V|$ and $m = |E|$.
\item Now suppose that in addition to a capacity $c(e)$, each edge $e$
  has a {\em lower bound} $\ell(e)$ and we are seeking a circulation
  $f$ that satisfies $f(e) \ge \ell(e)$ for all $e \in E$. Show how to
  find a such a circulation, or determine that one does not exist, by reducing to
max-flow. Your algorithm should run in time comparable to the
algorithms for max-flow on graphs with size parameters $n = |V|$ and
$m = |E|$.
\item Survey design. Suppose we have $n_1$ consumers and $n_2$
  products, and we are given a bipartite graph $G = (C \cup P, E)$
  with an edge $(c, p)$ to indicate that consumer $c$ owns product
  $p$. We want to perform a consumer satisfaction survey in which
  consumer $c$ is asked between $q_c$ and $q_c'$ questions and product
  $p$ is surveyed between $s_p$ and $s_p'$ times. We can only ask
  consumer $c$ about product $p$ if they own it.

 Given $G$, values
  $q_c, q_c'$ for each $c \in C$, and $s_p, s_p'$ for each $p \in P$,
  design an algorithm to determine whether the specified survey
  parameters are feasible, by formulating this as the problem of finding a
  circulation with lower bounds.
\end{enumerate}

\end{enumerate}
\end{document}
</pre></body></html>