%\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{\midterm}[2]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{0}
   \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 Final  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #1 \hfill Due: #2} }
      \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{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\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}
\midterm{June 3}{\bf June 10}


{\bf This is a final.} You may consult only the course notes and
the optional text (CLRS). {\em You may not collaborate.} The full honor code guidelines can be found in the course syllabus.


There are 4 problems on 2 pages. 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.} Good luck!


\medskip

{\bf Instructions for turning in the exam:} Please turn in your
exams to Diane Goodfellow in Annenberg 246 before noon on Tuesday
June 10.


\begin{enumerate}
\item Given subsets $S_1, S_2, \ldots, S_n$ of a universe $U$, and an
  integer $k$, a {\em maximum
    $k$-cover} is a collection of $k$ of the subsets that covers the
  maximum number of elements of $U$. Finding a maximum $k$-cover is NP-hard. Give a greedy approximation
  algorithm that achieves approximation ratio $e/(e-1)$. You may want
  to use the inequality $(1 - 1/x)^x \le 1/e$.

\item Show how to find a maximum matching in a tree $G = (V,E)$ in
  time $O(|E|)$ operations (where here an ``operation'' includes
  arithmetic operations on integers of magnitude $O(|E|)$). Hint: use
  dynamic programming.

\item Given a list of integers $a_1, a_2, \ldots, a_n$ we are
  interested in finding a subsequence having maximum sum; i.e., if for
  $i \le j$ we
  define $A_{i,j} = \sum_{i \le k \le j} a_k$, we want
  $i, j$ such that $A_{i,j}$ is maximum. Give a
  divide-and-conquer algorithm for this problem that uses $O(n\log n)$
  operations, where here an ``operation'' includes arithemetic
  operations on integers of magnitude $O(n|\max_i a_i|)$.


\item
Consider a directed graph $G = (V, E)$ with positive, integer capacities $c_e$ for each edge $e$. Here is an LP with variables $x_e$ for each edge $e \in E$ and $y_v$ for each $v \in V$ defined in terms of graph $G$ and two distinguished vertices $s$ and $t$, which represents the dual of the max-flow LP:

\noindent{minimize $\sum_{e \in E}c_ex_e$ subject to}
\begin{itemize}
\item $y_v - y_u + x_e \ge 0$ for all $e = (u,v) \in E$, and 
\item $y_s = 1$, and
\item $y_t = 0$, and 
\item $x_e \ge 0$ for all $e \in E$. 
\end{itemize}

You may assume that every vertex is reachable from $s$, and that every vertex can reach $t$.
\begin{enumerate}
\item Prove that the constraint matrix for this LP is totally unimodular. Hint: for one case in the proof, consider adding the rows of a submatrix.
\item Prove that the optimum value of this LP equals the value of the minimum $s-t$ cut in graph $G$. 
\end{enumerate}



\end{enumerate}

\end{document}
