%-*- 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{1}
    \lecturetitle{Homework\ }
    \lecturedate{Sep 10, 2007}
    \duedate{Sep 24, 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}[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
if 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{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: "1"
%%% End: