\documentclass[12pt]{article}
\usepackage{fullpage}
\addtolength{\topmargin}{-0.2in}
\addtolength{\textheight}{0.2in}
\newcommand{\Header}[1]{\begin{center} {\Large\bf #1} \end{center}}
\newcommand{\header}[1]{\begin{center} {\large\bf #1} \end{center}}
\newcommand{\orr}{\vee}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{1ex}
\newcommand{\andd}{\wedge}
\newcommand{\ep}{\varepsilon}
\newcommand{\de}{\delta}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\inv}[1]{\frac{1}{#1}}
\newcommand{\prob}{{\bf Prob}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\mathqed}{\mbox{\ \ \ \rule{6pt}{7pt}}}
\newcommand{\D}{{\cal D}}
\renewcommand{\Pr}{{\bf Pr}}
\newcommand{\pair}[1]{\langle #1 \rangle}
\newcommand{\mod}{\bmod}
\newcommand{\proj}{{\em proj}}
\newcommand{\proof}{{\em Proof. }}
\newcommand{\R}{{\bf R}}
\newcommand{\E}{{\bf E}}
\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\var}{{\bf var}}
\newcommand{\lesso}{<^o}
\newcommand{\eqtheta}{=^{\Theta}}
\newcommand{\comment}[1]{}
\newcommand{\bigcenter}[1]{\begin{center} {\large\bf #1} \end{center}}
\newcommand{\ceiling}[1]{\left\lceil #1 \right\rceil }
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor }

\addtolength{\textheight}{0.3in}
\begin{document}
\header{15-451 Algorithms, Fall 2011}
{\bf Homework \# 7} \hfill {\bf due: Thurs December 8, 2011}

\thispagestyle{empty}


\medskip

\hrule

\medskip
Please hand in each problem on a separate sheet and put
your {\bf name} and {\bf recitation} (time or letter) at the top of
each sheet.  You will be handing each problem into a separate box,
and we will then give homeworks back in recitation.
Remember: written homeworks are to be done {\bf individually}.  Group
work is only for the oral-presentation assignments.

\medskip

\hrule

\medskip
{\bf Problems:}
\begin{enumerate}
\item[{(25 pts) } 1.] {[NP-completeness and approximation algorithms]}

Let $\A$ be the set of pairs $(G,k)$ such that $G$ is a
graph with a vertex cover of size $k$ or less.    Let $\C$ be the set of
pairs $(G,k)$ such that $G$ has a vertex cover of size $k/2$ or less.
Notice that $\A \supseteq \C$ because if $(G,k) \in \C$ then clearly
$(G,k) \in \A$ also.

Determining whether a given input $(G,k)$ belongs to
$\A$ is NP-Complete (this is the Vertex-Cover problem), and also
determining whether a given input $(G,k)$ belongs to $\C$ is
NP-complete (since this is really the same problem).  

Describe a set $\B$ such that $\A \supseteq \B
\supseteq \C$ but membership in $\B$ can be decided in polynomial
time (and explain why membership in $\B$ can be decided in polynomial
time).  So this is just like the situation on Mini 5.  Hint: think
approximation algorithms.


\item[{(25 pts) } 2.] {Randomized Rent-or-Buy}

Consider the rent-or-buy problem in the simple case that the cost to
buy skis is twice the rental cost.  The optimal deterministic
algorithm (as discussed in class) is: ``rent once, then buy'' for a
competitive ratio of $3/2$.  In this problem we will consider {\em
randomized} algorithms.  For a randomized algorithm, the definition of
competitive ratio is $\max_{\sigma} \E[\mbox{alg
cost}(\sigma)]/OPT(\sigma)$, where ``$\sigma$'' is the number of times
we go skiing.

We can think of competitive analysis as a 2-player game: we pick a
strategy, the adversary picks how many times $\sigma$ we go skiing,
and then we are charged the above ratio.
It turns out that if the purchase cost is twice the rental
cost, there are only two choices for the adversary that we need to
worry about: $\sigma=1$ or $\sigma=\infty$. 
Because of this, there are only two deterministic strategies that make
sense for us to randomize over: either (1) buy right away, or (2) rent once
and then buy if we go skiing again.

\begin{enumerate}
\item Draw out a matrix corresponding to this game.  
The matrix should have two rows (one for ``buy right away'' and one
for ``rent once then buy'') and two columns (one for ``$\sigma=1$''
and once for ``$\sigma=\infty$'').  
The cells in the matrix should give the competitive ratio 
of that algorithm in that event.

\iffalse
{\sf\large
\begin{center}
\begin{tabular}{c|c|c|}
           & ski once & ski forever \\ \hline
buy        &          &             \\
right away &          &             \\ \hline
rent once  &          &             \\
then buy   &          &             \\ \hline
\end{tabular}
\end{center}}
\fi

\item The minimax optimal strategy for the row player in this matrix
game gives the randomized algorithm with the best competitive ratio.
What is that strategy, and what is the minimax value of the game (the
optimal randomized competitive ratio)?

\item To complete the argument, prove the two assertions made above
that allowed us to reduce the problem to the 2-by-2 case.
Specifically,
\begin{enumerate}
\item Show that we only need to
consider $\sigma=1$ and $\sigma=\infty$ by arguing why for any
randomized algorithm $\A$, and any $\sigma>1$,
we have $\E[\A(\sigma)]/OPT(\sigma) \leq
\E[\A(\sigma+1)]/OPT(\sigma+1).$
\item Assuming now that either $\sigma=1$ or $\sigma=\infty$, argue
why the optimal randomized algorithm would put zero probability on the
deterministic strategy ``rent $i$ times then buy'' for any $i>1$.
\end{enumerate}


\end{enumerate}

\item[{(25 pts) } 3.] {[Random-access\footnote{``Random access'' as
in random-access memory, i.e., as opposed to sequential-access.  Not
``random'' as in probability.} long division]}. 

Give a polynomial time algorithm to find the $N$th digit of the
fraction $A/B$, where $A$, $B$ and $N$ are all given in binary.

Input: integers $(A,B,N)$ in binary notation, where $A < B$.   

Let $ 0.d_1 d_2 d_3 \cdots$ be the decimal expansion of the fraction
$\frac{A}{B}$.

Output: $d_N$.

\smallskip

Note: the key thing here is that your algorithm's running time should
be polynomial in $\log N$ (and $\log A$ and $\log B$).  The standard
way of doing long division would instead be polynomial in $N$.  In
particular, the standard long division would look like this:
\begin{quote}
  for $i = 1$ to $N$ do:\\ 
\hspace*{0.2in} $d_i = 10 A$ div $B$;\\
\hspace*{0.2in} $A = 10 A$ mod $B$;
\end{quote}
where ``div'' is integer division.


\item[{(25 pts) } 4.] {FFT}

Consider the following problem.  You are given a string $P$ of 1's and
$*$'s (the ``pattern''), and a string $T$ of 0's
and 1's (the ``text'').  Your job is to find all places where the
pattern $P$ appears in text $T$, where a star can match either a 0 or
a 1.  For instance, if $P =$ {\tt 11$*$1} and $T = $ {\tt
10111101}, then $P$ appears twice in $T$: once starting at the 3rd
position in $T$ and once starting at the 5th position in $T$.

Say $P$ has length $n$ and $T$ has length $m$, where $m>n$.  There is
a simple $O(mn)$-time algorithm to solve this problem: try all
$O(m)$ possible starting positions, and for each one, check in time
$O(n)$ to see if $P$ matches there.  

Show how you can use the FFT to solve this problem in time only $O(m
\log m)$.  

[Hint: you may wish to reverse $P$.  Note: you do not need to explain
the inner workings of the FFT algorithm.]

\end{enumerate}




\end{document}
