%-*- LaTeX -*-

\NeedsTeXFormat{LaTeX2e}
\documentclass{assign}
\usepackage{newcent}
\usepackage{amsmath,amsthm,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{}
    \lecturetitle{Final }
    \lecturedate{Dec 7, 2007}
    \duedate{Dec 11, 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}
\newtheorem*{defn}{Definition}
% \numberwithin{equation}{section}
\renewcommand{\thesection}{\arabic{section}}
\begin{document}
%\label{begin}

\textbf{Instructions:}
\begin{itemize}
\item The exam MUST be submitted no later than 5pm Tuesday Dec 11, whether
  electronically or by hand.
\item The exam is open-book: you may use any reference material from the
  textbook, or from the Cormen/Leiserson/Rivest/Stein book. You MAY NOT
  use answers found on the web.
\item If you need a desired result (running time of Kruskal's algorithm,
  etc) that is not directly related to the problem you're solving, you may
  cite it. For example, you can say, ``We can compute an MST in $O(m\log
  n)$ time using Kruskal's algorithm (Kleinberg/Tardos, Chapter
  4.5). Citations must come from one of the two textbooks indicated
  above.
\item This is an examination: \textbf{consultations are not permitted}.
\item \textbf{Unless clearly specified, all statements require proofs}.
\end{itemize}

\newpage


\section{}

We return to 3SAT once again for this problem. Assume we are given an
instance of 3SAT in which 
\begin{itemize}
\item There are $m$ clauses and $n$ variables.
\item Each clause has \emph{exactly} 3 literals
\item There is a unique satisfying assignment.
\end{itemize}

We propose the following ``random walk'' strategy.
\begin{enumerate}
\item Start with a \emph{random} assignment of values to the variables
\item Repeat $n$ times:
\item If all clauses are satisfied, we are done. Else,
\item Take any clause that remains unsatisfied, pick one of its variables
  with equal probability, and flip its value, thus satisfying this clause
  (of course, other clauses might become unsatisfied)
\end{enumerate}

\begin{enumerate}[label=\alph*)]
\item Show that the above procedure finds a satisfying assignment with
  probability $(2/3)^n$
\item Use the above fact to find an algorithm that guarantees to find a
  satisfying assignment. Give a bound on its running time and specify
  whether this bound is expected, or worst-case.
\end{enumerate}
\newpage 


\section{}

The Xenopic rabbits spend their lives jumping from the place of their birth
to Carrotopia, the semi-mythical land of the everlasting carrots. But these are weak
rabbits; every time they jump a distance, they wear down, and can only
jump half the distance the next time. Life starts with a mighty leap
halfway towards Carrotopia, and progresses by halving ever after.

One enterprising youngster Monte C. feels that life is too predictable and decides
to spice things up. Rather than following the boring deterministic ways of
his elders, he decides to indulge in some illicit randomization. 

Let's say that Carrotopia is at the center of the land: we call
this point $0$. The rabbits are born far away, in a small town called
$N$\footnote{The remaining letters washed away in a deluge. Stuff
  happens.}. Coincidentally, $N$ happens to be exactly $N$ miles away from
Carrotopia. 

It turns out that randomness works differently in different parts of the
country. In fact, at $x$ units away from Carrotopia, a random sample
of the reals generates a number that has an expected value of $g(x)$. Monte starts from
home, and rolls a die; he then jumps the value that comes up. He then
computes a random sample from the town he's in, rolls it, and jumps
again. All he can rely on is the fact that $g(x)$ is a monotonically
increasing function of $x$ (for example, the deterministic rabbits are
operating with a \emph{deterministic} function $g(x) = x/2$.

When should we expect Monte to reach Carrotopia ? Your answer should be in
terms of $N$ and $g(x)$ (don't expect a completely closed form). 

\newpage

\section{}


\subsection{}

An instance of \textsc{knapsack} consists of $n$ items, each with weight
$w_i$ and profit $p_i$. The goal is to maximize the total profit of items
thrown into a sack that can carry a total load of at most 1. 

\textsc{Knapsack} is NP-Complete. Consider however the following \emph{fractional}
variant: we're allowed to pick an $\alpha_i$ fraction of item $i$, and
thus the new goal is to maximize the quantity $\sum \alpha_i p_i$, subject to
the constraint $\sum \alpha_i w_i \le 1$. Give a strongly polynomial time
algorithm that finds the optimal fractional knapsack solution. Your
solution will consist of the fractions $\alpha_i$ (note that any item not
picked merely has $\alpha_i = 0$).



\newpage

\section{}


We say that a sequence of numbers $x_1, x_2, \ldots, x_n$ is
\emph{oscillating} if for any odd index $i$, $x_i \ge x_{i+1}$, and for
any even index $i$, $x_i \le x_{i+1}$. For example, the sequence $\{ 2, 1,
7, 3, 10, 5, 8\}$ is oscillating.

Design an efficient algorithm to find a longest oscillating subsequence of
an input sequence of numbers. 

\newpage


\section{}


We've seen how to multiply two $n$-bit integers in time $O(n^{\log
  3})$. Assume now that we have a computer with a word length of
$\sqrt{n}$, which means that we can multiply two $\sqrt{n}$-bit integers
in constant time. 

Under this cost model, show that two $n$-bit integers can be multiplied in
time $o(n^{1.3})$. 

\newpage


\section{}

We revisit the problem of computing a maximum matching in a bipartite
graph $G = (L \cup R, E)$, where $|L \cup R| = n, |E| = m$. In the
max-flow formulation we studied earlier, an augmenting path from the
source to sink consisted of one edge from the source, a series of edges
originating at an unmatched node in $L$ and ending at another unmatched
node in $R$, and finally an edge to $t$. 

Let's ignore the edges from $s$ and to $t$. What we have left is a path
that alternates between edges not in the current matching and edges that
are. The importance of such a path is this: it always has odd length (say
$2k+1$), and of these edges, $k+1$ are not in the matching, and $k$
are. This means that given the current matching $M$ and such an augmenting
path $P$, the new set of edges $M' = M \Delta P$ (where $A \Delta B = (A - B)
\cup (B-A)$ is the symmetric difference between sets $A$ and $B$) is of
size $|M'| = |M|+1$. 

Thus, repeatedly finding such augmenting paths and computing the resulting
symmetric difference allows us to continually increase the size of the
matching till we reach the maximum.



\subsection{}

Let $M$ and $M'$ be two matchings, where $|M| \le |M'|$. Show that in the
graph induced by the edges of  $M \Delta M'$, each vertex has degree at
most two. Prove that this implies that this graph consists of cycles and
paths, and show that it contains at least $|M'| - |M|$ vertex-disjoint
augmenting paths with respect to $M$.

\subsection{}

Suppose we only consider augmenting paths of length 1 (i.e each augmenting
path consists of a single edge between two unmatched nodes). Show that the
matching we obtain by augmenting by \textbf{all} such paths is a
(1/2)-approximation to the maximum matching. 


\subsection{}

Suppose we now consider augmenting paths of length at most $2\ell+1$. Generalize
the above result to show that the best matching thus obtained is an
$(\ell/(\ell+1))$-approximation to the maximum matching.


\subsection{}
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: