%\def\solutionMode{TRUE}
\documentclass[12pt]{article}
\usepackage{algorithm2e}
%\def\NoAlgorithmEnv{1}
\usepackage{573}
%
% ======================================================================
\begin{document}
\noindent {\LARGE\bf \Course{}: \CourseName{}, \Semester{}}
\\[1ex]
{\Large\bf Homework 5, due Monday, December 2, 23:59:59, \Year}
\\[0.25in]
{\bf Version 1.0}
\smallskip
\noindent
\hrule
\hrule
\hrule
% ----------------------------------------------------------------------
\medskip
\noindent
Neatly print your name(s), NetID(s) on each submitted question.
Remember that you have to submit each question on a separate
page. each student should submit his own homework. If you are on
campus, submit the homework by submitting it in the homework boxes in
the basement of SC.
% ----------------------------------------------------------------------
\bigskip
%----------------------------------------------------------------------
\smallskip
%\newpage
%\thispagestyle{empty}
\bigskip
\noindent\fbox{\begin{minipage}{0.99\linewidth}
``Is there anything in the Geneva Convention about the rules of war
in peacetime?'' Stanko wanted to know, crawling back toward the truck.
``Absolutely nothing,'' Caulec assured him. ``The rules of war apply
only in wartime. In peacetime, anything goes.''
\hspace*{2cm} -- Gasp, Romain Gary
\end{minipage}}
\SaveIndent%
\section*{Required Problems}
% \newcommand{\HWProblem}[3]{\item \textsc{#1}\\
% #2} \newcommand{\GreedyIndep}{\Algorithm{Greedy{}I{n}d{e}p}}
% \renewcommand{\th}{th\xspace}
% ======================================================================
\begin{compactenum}[\color{red} \huge \bf 1.]%
\item \HWProblem{40}{Sorting networks stuff}%
{
\begin{compactenum}[(A)]
\item \points{5} Prove that an $n$-input sorting network
must contain at least one comparator between the $i$\th and
$(i+1)$st lines for all $i=1,2,...,n-1$.
\item \points{20} Prove that in a sorting network for $n$
inputs, there must be at least $\Omega( n\log n)$
gates. For full credit, your answer should be short, and
self contained (i.e., no reduction please).
[As an exercise, you should think why your proof does not
imply that a regular sorting algorithm takes $\Omega(n \log
n)$ time in the worst case.]
\item \points{5}
Suppose that we have $2n$ elements
$\permut{a_1,a_2,...,a_{2n}}$ and wish to partition them
into the $n$ smallest and the $n$ largest. Prove that we
can do this in constant additional depth after separately
sorting $\permut{a_1,a_2,...,a_n}$ and
$\permut{a_{n+1},a_{n+2},...,a_{2n}}$.
\item \points{10}
Let $S(k)$ be the depth of a sorting network with $k$
inputs, and let $M(k)$ be the depth of a merging network
with $2k$ inputs. Suppose that we have a sequence of $n$
numbers to be sorted and we know that every number is
within $k$ positions of its correct position in the sorted
order, which means that we need to move each number at most
$(k-1)$ positions to sort the inputs. For example, in the
sequence 3 2 1 4 5 8 7 6 9, every number is within 3
positions of its correct position. But in sequence 3 2 1 4
5 9 8 7 6, the number 9 and 6 are outside 3 positions of
its correct position.
Show that we can sort the $n$ numbers in depth
$S(k)+2M(k)$. (You need to prove your answer is correct.)
\end{compactenum}%
}{}{}{}
\item \HWProblem{30}{Computing Polynomials Quickly}{ %
% \points{30}
In the following, assume that given two polynomials $p(x),q(x)$
of degree at most $n$, one can compute the polynomial remainder
of $p(x) \bmod q(x)$ in $O(n \log{n})$ time. The
\emphi{remainder} of $r(x) = p(x) \bmod q(x)$ is the unique
polynomial of degree smaller than this of $q(x)$, such that
$p(x) = q(x) * d(x) + r(x)$, where $d(x)$ is a polynomial.
Let $p(x) = \sum_{i=0}^{n-1} a_i x^i$ be a given polynomial.
\begin{compactenum}[(A)]
\item \points{8} Prove that $p(x) \bmod (x-z) = p(z)$, for
all $z$.
\item \points{8} We want to evaluate $p(\cdot)$ on the
points $x_0, x_1,\ldots, x_{n-1}$. Let
\[
P_{i j}(x) = \prod_{k=i}^j ( x - x_k)
\]
and
\[
Q_{i j}(x) = p(x) \bmod P_{i j}(x).
\]
Observe that the degree of $Q_{i j}$ is at most $j-i$.
Prove that, for all $x$, $Q_{kk}(x) = p(x_k)$ and
$Q_{0,n-1}(x) = p(x)$.
\item \points{6} Prove that for $i \leq k \leq j$, we have
\[
\forall x \;\;\; Q_{ik}(x) = Q_{ij}(x) \bmod P_{ik}(x)
\]
and
\[
\forall x \;\;\; Q_{kj}(x) = Q_{ij}(x) \bmod P_{kj}(x).
\]
\item \points{8} Given an $O(n \log^2 n )$ time algorithm
to evaluate $p(x_0), \ldots, p(x_{n-1})$. Here $x_0,
\ldots, x_{n-1}$ are $n$ given real numbers.
\end{compactenum}
}{}
\item \HWProblem{30}{Linear time Union-Find.}{
\begin{compactenum}[(A)]
\item \points{3} With path compression and union by rank,
during the lifetime of a Union-Find data-structure, how many
elements would have rank equal to $\floor{\lg{n}-5}$, where
there are $n$ elements stored in the data-structure?
\item \points{3} Same question, for rank
$\floor{(\lg{n})/2}$.
\item \points{6} Prove that in a set of $n$
elements, a sequence of $n$ consecutive
\textsc{Find} operations take $O(n)$ time in total.
\item \points{3} Write a non-recursive version of
\textsc{Find} with path compression.
%\end{enumerate}
\item \points{9} Show that any sequence of $m$
\textsc{Make{}Set}, \textsc{Find}, and \textsc{Union}
operations, where all the \textsc{Union} operations
appear before any of the \textsc{Find} operations,
takes only $O(m)$ time if both path compression and
union by rank are used.
\item \points{6} What happens in the same situation
if only the path compression is used?
\end{compactenum}
}{}
\end{compactenum}
\end{document}