%-*- LaTeX -*-

\NeedsTeXFormat{LaTeX2e}
\documentclass{assign}
\usepackage{newcent}
\usepackage{amsmath,amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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{2}
    \lecturetitle{Homework\ }
    \lecturedate{Sep 10, 2008}
    \duedate{Sep 24, 2008}
    \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{Recurrences}
\label{sec:recurrences}

Solve the following recurrences: in all cases, the answer should be of the
form $T(n) = \Theta(f)$. In all recurrences, you may assume that $T(1) =
1$, and $T(2)$, if needed, is some arbitrary number $a$.

\begin{itemize}
\item $T(n) = 7T(n/4) + O(n)$
\item $T(n) = 2T(n/2) + O(n\log^2 n)$
\item $T(n) = \log n T(n/\log n) + n$
\item $T(n) = \frac{\pi T(n-1)}{\sqrt{2}T(n-2)}$ (this is easier than you think)
\item $T(n) = 5T(n-1) - 4T(n-2)$
\end{itemize}



\section{Checking if $x = y_1 + y_2$ (CLRS 2.3-7)}
\label{sec:checking-if-x}

Describe an $O(n\log n)$-time algorithm that, given a set $S$ of $n$
integers and another integer $x$, determines whether or not there exist
two elements in $S$ whose sum is exactly $x$. 

\section{Computing Medians (KT 5.1)}
\label{sec:comp-forc-force}

You are given two databases, each containing $n$ numbers. You can assume
that all the $2n$ numbers are distinct. A \emph{query} consists of asking
a database what its $k^{\text{th}}$ smallest number is. Show how you can
compute the median of the set of $2n$ numbers (specifically, the
$n^{\text{th}}$ smallest number) using $O(\log n)$ queries to the
databases. 

\section{Analyzing 3SAT}
\label{sec:analyzing-3sat}

As we shall see when we study NP-hardness, 3SAT is a canonical NP-complete
problem. An instance of 3SAT is a boolean formula $\Phi$ consisting of $m$
\emph{clauses}: 

\[ \Phi = c_1 \wedge c_2 \dots c_m\]
The $\wedge$ represents AND: the function $\Phi$ is true iff each of the
$c_i$ are true. Each clause is written as the OR of three literals:
\[ c_i = v_{i_1} \vee v_{i_2} \vee v_{i_3} \]
where each $v_{i_j} = x_k$ or $\overline{x_k}$, where $x_k, 1 \le k \le n$ is a variable
that takes the value \texttt{true} or \texttt{false} and $\overline{x_k}$ is
the negation of $x_k$. The ``3'' in 3SAT comes from the fact that each
clause contains three literals. 

An example 3SAT instance on 

\[ \Phi = (x_1 \vee x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee
x_4 \vee x_3) \wedge (x_1 \vee \overline{x_2} \vee \overline{x_4}) \]

Notice that $m = O(n^3)$; this is because there are $\binom{n}{3}$ ways of
choosing the variables to be used in a clause, and there are $2^3 = 8$
ways of choosing these three variables to be negated or un-negated.

A 3SAT instance is \emph{satisfiable} if there exists a way of assigning
values \texttt{true} and \texttt{false} to the $x_i$ such that $\Phi$ is
true. It is unsatisfiable if no such assignment exists. The above example
is satisfiable, because we can set $x_1 = \mathtt{true}, x_2 =
\mathtt{false}, x_3 = \mathtt{false}, x_4 = \mathtt{true}$, which yields
$\Phi = (\mathtt{true}) \wedge (\mathtt{true}) \wedge (\mathtt{true}) =
\mathtt{true}$. Notice that we can 
easily check whether $\Phi$ is satisfiable in time $O(m \cdot 2^n)$ by
trying all possible assignments, and checking each one. 


However, we can actually do slightly better than this. Take a 3SAT formula
$\Phi$, and rewrite it as 
\begin{align*}
  \label{eq:1}
  \Phi &= c_1 \wedge \Phi'  \\
  &= (v_1 \vee v_2 \vee v_3) \wedge \Phi'
\end{align*}
By distributivity, we can rewrite this as 
\[ \Phi = (v_1 \wedge \Phi') \vee (v_2 \wedge \Phi') \vee (v_3 \wedge
\Phi')  \]

Now, $(v_1 \wedge \Phi')$ can only be true if both $v_1$ and $\Phi'$ are
true. Let $\Phi'|_v$ denote $\Phi'$ with all instances of the literal $v$
set to \texttt{true}. Then clearly  $(v_1 \wedge \Phi') = (v_1 \wedge
\Phi'|_{v_1})$. Notice that $\Phi'|_{v_1}$ \textbf{is an instance of 3SAT with one
fewer variable}, since $v_1$ is set to \texttt{true}.

However, if $\Phi'|_{v_1}$ is not satisfiable, then we know that $v_1$
must be set to \texttt{false}. Therefore, if $\Phi$ is satisfiable while
the first clause $(v_1 \wedge \Phi')$ is unsatisfiable, then one of the
other two clauses must be satisfiable \textbf{with $v_1$ set to
  \texttt{false}}. 

In other words, 
\[ \Phi = (v_1 \wedge \Phi'|_{v_1}) \vee (v_2 \wedge \Phi'|_{\overline{v_1}v_2}) \vee (v_3 \wedge
\Phi'|_{v_3})  \]

Repeating this argument again, 
\[ \Phi = (v_1 \wedge \Phi'|_{v_1}) \vee (v_2 \wedge \Phi'|_{\overline{v_1}v_2}) \vee (v_3 \wedge
\Phi'|_{\overline{v_1}\overline{v_2}v_3})  \]

Use this expression to derive an algorithm for checking satisfiability
that runs in time $o(2^n)$. \textbf{HINT:} Write down the implied recurrence.


\paragraph*{Note.} 
\label{sec:note}

The best known algorithm for 3SAT runs in time
approximately $O(1.473^n)$. Your solution will be worse than this.



\section{Programming Assignment}


\begin{enumerate}
\item Go to the ACM Online judge at
  \url{http://icpcres.ecs.baylor.edu/onlinejudge/index.php}. 
\item From the \texttt{Brows Problems} section, locate Problem 10245:
  \textbf{The Closest Pair problem}. This can be found under \texttt{Root}
  $\rightarrow$ \texttt{Contest Volumes} $\rightarrow$ \texttt{Volume
    CII}. The direct URL is
  \url{http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1186}
\item Submit a solution for this problem (see the Submit button at the top
  right), and verify using \texttt{My Statistics} on the left sidebar that
  it was   accepted and ran successfully. NOTE: the program should take
  input from 
  the command line.  
\item Submit your code using the CADE handin software.
\end{enumerate}

\paragraph*{Note}
\label{sec:note-1}
I am particularly curious as to whether solutions that are NOT based on
divide-andconquer can come in under the time bound. If you can come up
with such a solution, do let me know.
% \section{Computing an FFT}
% \label{sec:computing-an-fft}

% Trace the FFT-based algorithm for multiplying two polynomials on the
% inputs $p(x) = 3x^3 + x^2 - 4x + 1$ and $q(x)= x^3 - 2x^2 + 7x -2$. Your trace should have the following
% steps:
% \begin{enumerate}
% \item Generate the point representation of $p(x)$
% \item Generate the point representation of $q(x)$
% \item Multiply the point representations
% \item Perform the interpolation step
% \item Verify that the result is indeed $p \cdot q$
% \end{enumerate}

% Points will be deducted for missing steps. The point of this exercise is
% not just to get the correct answer, but to show the steps involved. Since
% the degree of the product is at most $6$, you can use the $8$-input
% version of the FFT described in class. 

% \section{Pattern Matching*}
% \label{sec:fft}

% In standard string matching, you are given two strings over an alphabet
% $\Sigma$:  \emph{pattern} $p$ of length $k$  and a \emph{text} $t$ of
% length $n \ge k$. The goal is to find all positions $i$ of $t$ where $t$ and $p$
% match:

% \[ \forall 0\le j \le k-1, t[i+j] = p[j] \]

% In this problem, we'll consider a variant of string matching where $\Sigma
% = \{0,1\}$ (i.e we work with a binary alphabet), and we only wish to make
% sure that if $p$ has a 1 in a particular position, then $t$ has a 1 in
% that same position. Formally, we can define a match at position $i$ as:

% \[ \forall 0\le j \le k-1, t[i+j] \ge p[j] \]

% \begin{figure}[htbp]
%   \centering
%   \includegraphics[width=4in]{pm.pdf}
% \end{figure}

% Given an algorithm running in time $O(n\log n)$ that takes as input a
% pattern and text as above, and outputs a vector $v$ of length $n-k$ such that $v[i]=1$ if
% there is a match at position $i$ in the text. For the above example, your
% algorithm should output $v = ( 0, 0, 1, 0 )$. Assume that $k =
% \Theta(n)$. 

% \textbf{HINT:} Rather than trying to compute $v$, it might be easier to
% compute $v', v'[i] = 1 - v[i]$, the \emph{mismatch} vector. Now, think of
% expressing $p, t, v'$ as polynomials.


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "2"
%%% End: