%-*- 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{Midterm }
    \lecturedate{Oct 17, 2007}
    \duedate{Oct 19, 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 Friday Oct 19, whether
  electronically or by hand.
\item Submit each problem on separate sheets, using the midterm question
  as the first page of each set.
\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 Unless clearly specified, all statements require proofs. 
\end{itemize}

\textbf{Choices:}

You must do questions~\ref{sec:1} and~\ref{sec:2}, and you can do
\textbf{ANY THREE} of the remaining five questions. Submit this
cover sheet along with your solutions, indicating which of the five
questions you chose to answer.

\begin{description}
\item[\ref{sec:3}] \underline{\ \ \ \ \ \ \ \ }
\item[\ref{sec:4}] \underline{\ \ \ \ \ \ \ \ }
\item[\ref{sec:5}] \underline{\ \ \ \ \ \ \ \ }
\item[\ref{sec:6}] \underline{\ \ \ \ \ \ \ \ }
\item[\ref{sec:7}] \underline{\ \ \ \ \ \ \ \ }
\end{description}
\newpage

\section{}
\label{sec:1}
%Each of the following questions has one of these five answers:
% \begin{table}[h]
%   \centering
%   \begin{tabular}{c|c|c|c|c} 
%     A & B & C & D & E \\ \hline
%     $\Theta(1)$ & $\Theta(\log n)$ & $\Theta(n)$ & $\Theta(n\log n)$ & $\Theta(n^2)$
%   \end{tabular}
% \end{table}

\subsection{}


For each question, write down the correct answer in the form $\Theta(f)$. No explanations are
needed. 
\begin{enumerate}[label=\alph*)]
\item What is $\sum_{i=1}^n n/i$ ?
%\item What is $\sum_{i=1}^n i/n$ ?
\item What is the solution of $T(n) = T(n-1) + 1/n^2$ ?
\item What is the solution of $T(n) = 2T(\lceil \frac{n+27}{2} \rceil) +
  5n - 7\sqrt{\log n} + 56/n$ ?
\item What is the solution of $T(n) = T(\sqrt{n}) + 1$ ? 
\item The Fibonacci number $F_n = F_{n-1} + F_{n-2}$. $F_0 = 0, F_1 =1$. 
How many \emph{bits} are needed to write down $F_n$ ? 
\end{enumerate}


\subsection{}

Let 
\[ T(n,m) = T(n-1,m) + T(n-1,m-1), T(n,0) = T(n,n) = 1\]
Show that $T(n,m) = O(n^m)$.
\newpage

\section{}
\label{sec:2}

\subsection{}


\begin{defn}[Interval Scheduling]
  Given a collection of intervals $\{ (s_1, t_1), \ldots (s_n,t_n)\}$ on
  the line, and a bound $k$, does the collection contain a subset of
  \emph{non-overlapping} intervals of size at least $k$ ? 
\end{defn}
Recall that we encountered the optimization version of this problem (find
the largest subset of nonoverlapping intervals) when studying greedy
algorithms.  Answer the two questions below with one of the following
three choices, and give your reasoning.
\begin{itemize}
\item Yes
\item No
\item Unknown, because the answer would resolve P vs NP. 
\end{itemize}
\begin{description}
\item[Q1] Does Interval Scheduling $\le_p$ Vertex Cover ?
\item[Q2] Does Independent Set $\le_p$ Interval Scheduling ?
\end{description}


\subsection{}

Your friend is planning to hold a Christmas party. He wants to take a picture of all the
participants, including himself, but he is quite shy and thus cannot take a picture of a person
whom he does not know very well. Since he has only shy friends, everyone at the party is
also shy. After thinking hard for a long time, he came up with a seemingly good idea:
\begin{itemize}
\item He brings a disposable camera to the party.
\item Anyone holding the
  camera can take a picture of someone they know very well, and then pass
  the camera to that person.
\item In order not to waste any time, every person  must have their picture
  taken exactly once.
\end{itemize}

 Although there can be some people he does not know very well, he knows completely who
knows whom well. Thus, in principle, given a list of all the participants, he can determine
whether it is possible to take all the pictures using this idea. But how quickly?
Either describe an efficient algorithm to solve his problem, or show that the problem is
NP-complete.

\newpage


\section{}
\label{sec:3}

In this problem, we'll be analyzing the resistance of electrical
networks. Here's all that you need to know about electrical networks:

\begin{enumerate}
\item If we have two resistors connected in series, their end-to-end
  resistance is the sum of the two resistances.
  \begin{figure}[h]
    \centering
    \includegraphics[width=3in]{series}
  \end{figure}
\item For two resistors connected in parallel, the end-to-end resistance
  is the reciprocal of the sum of the reciprocals. 
  \begin{figure}[h]
    \centering
    \includegraphics[width=3in]{parallel}
  \end{figure}
\end{enumerate}

In the figure below, all resistors
have magnitude $1\Omega$\footnote{The Ohm ($\Omega$) is the unit of
  resistance.}, and the resistors form a complete binary tree of depth
$n$. Compute the exact expression for the resistance between the left-most and
right-most endpoints of the circuit, as a function of $n$. (Do not use
$O()$ notation)
  \begin{figure}[h]
    \centering
    \includegraphics[width=3in]{btree}
  \end{figure}


\newpage

\section{Shuffles}
\label{sec:4}

A \emph{shuffle} of two strings $s, t$ is an interleaving of the letters
of the strings that preserves the order of each string. For example, 
valid shuffles of ``nondeterministic'' and ``polynomial'' are 
\begin{quote}
non\raisebox{-1ex}{polynom}determin\raisebox{-1ex}{ia}ist\raisebox{-1ex}{l}ic\hfill
po\raisebox{-1ex}{nondeter}lyno\raisebox{-1ex}{ministic}mial
\end{quote}

Given  strings $A[1\ldots n], B[1\ldots m]$ and $C[1\ldots n+m]$, design
an algorithm that runs in time $O(nm)$ and checks whether $C$ is a valid
shuffle of $A$ and $B$. 

\textbf{HINT:} Consider constructing a table $M[i,j]$, where $M[i,j] = 1$
if the string $C[1\ldots i+j]$ is a valid shuffle of $A[1\ldots i]$ and
$B[1\ldots j]$. 
\newpage 

\section{Minimum-altitude connected subgraphs}
\label{sec:5}
\textbf{Note:} This is problem 4.20 in the textbook

Let $G = (V,E)$ be a graph with a height function $c : E \rightarrow
\reals^+$ defined on the edges. Denote the \emph{height} of a path as the
maximum height of any edge along the path. For two vertices $v, u$, we say
that the path $p$ connecting $(v,u)$ is winter-optimal if the height of
$p$ is minimum over all paths connecting $v$ and $u$. 

Fix a subgraph $G' = (V, E')$ of $G$, formed by picking a subset of edges
$E' \subseteq E$.

$G'$ is said to be a \emph{minimum-altitude connected subgraph} if
\begin{itemize}
\item $G'$ is connected
\item For all pairs of vertices $v,u$, their winter-optimal path in $G'$
  has height at most the height of their winter-optimal path in $G$. 
\end{itemize}

Prove or disprove (with a counter example) the following statements
\begin{enumerate}[label=\alph*)]
\item The MST of G with edge weights $c$ is a minimum-altitude connected subgraph
\item A subgraph $G' = (V, E')$ is a minimum-altitude connected subgraph
  if and only if it contains the edges of the minimum spanning tree
\end{enumerate}
\newpage 

\section{Pattern Matching}
\label{sec:6}

Let $p$ and $t$ be two binary strings of length $k$ and $m$ respectively. We say that $p$ \emph{matches} $t$
at position $i < m-k$ if 
\[ \forall_{j = 0}^{k-1}\  (p[j] \le t[i+j]) \] 

Informally, this means that if $t[i+j]$ is 0, then $p[j]$ must be
zero. Notice that it's permitted for $p[j] = 0$ when $t[i+j] = 1$. 

We would like to find all positions $i$ where $p$ matches $t$. Let $c$ be
the \emph{match array}: $c[i] = 1$ if and only if $p$ matches $t$ at
position $i$, and is zero otherwise. Here's an example:

\begin{figure}[h]
  \centering
  \includegraphics[width=3in]{mismatch}
\end{figure}

Suppose we define an array $\tilde{c}$ by the formula
\[ \tilde{c}[i] = \sum_{j=0}^{k-1} p[j] \cdot t[i+j] \]
Suppose $p$ has $n$ 1s in it. Then it's easy to see that $\tilde{c}[i] =
n$ whenever there's a match, and $\tilde{c}[i] < n$ when there is no 
match. This is because if there's a match, each 1 in $p$ matches a 1 in
$t$, and they sum up. All other multiplications are 0. 

So if we can compute $\tilde{c}$, we can easily compute $c$. 

\begin{problem}
  Given strings $p$ and $t$, construct the array $\tilde{c}$. Assuming
  that the maximum number of 1s in either $p$ or $t$ is $n$, your
  algorithm should run in time $O(n\log n)$.
\end{problem}

\textbf{HINT:} Think of $p$ and $t$ as polynomials.

\newpage 

\section{Set Splits}
\label{sec:7}

\begin{problem}
  Given a universe $S$, and a collection ${\cal C}$ of subsets of $S$, is
  there a partition of $S$ into $S_1$ and $S_2$ such that for any set $C
  \in {\cal C}$, $C$ intersects both $S_1$ and $S_2$ ? 
\end{problem}

Show that this problem is NP-Complete. 

\textbf{HINT:} You may find it useful to consider the NP-Complete problem
Not-All-Equal-3SAT. This consists of instances of 3SAT, where the
constraint is that in any assignment of values that satisfies the
instance, \emph{no clause has all its literals set to 1}. Obviously, no
clause in a satisfying assignment can have all its literals set to zero,
which motivates the name of the problem. 

Warning: the reduction proceeds in two steps, with one intermediate problem.

\end{document}

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