\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{fancybox}
\setlength{\unitlength}{1mm}
\newcommand{\APPLE}{\textsf{\sc Apple}}
\newcommand{\RBS}{\textsf{\sc RandomizedBinarySearch}}
%%%%%%%%%%%%Separating rule above/below figures%%%%%%%%%%%%%%%%%%%%%
\setlength{\textfloatsep}{5ex}
\newcommand{\topfigrule}{\noindent\rule[-0.5cm]{\textwidth}{0.2mm}\vspace*{-6pt}\noindent}
\newcommand{\botfigrule}{\noindent\rule[-0.5cm]{\textwidth}{0.2mm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% Capsule %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\capsule}[2]{\vspace{0.5em}
\shadowbox{%
\begin{minipage}{.90\linewidth}%
\textbf{#1:}~#2%
\end{minipage}}
\vspace{0.5em} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}
\begin{document}
\begin{center} \Large\bf
COMP 3804 --- Assignment 1
\end{center}
\noindent {\bf Due:} Sunday February 7, 23:59.
\vspace{0.5em}
\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
cuLearn.
\begin{center}
\hfill\shadowbox{
\begin{minipage}{.90\linewidth}
{\textsf{Use the following format to name your file:
\[ {\tt LastName\_StudentId\_a1.pdf}
\]
}}
\end{minipage}
}
\end{center}
\item {\bf Late assignments will not be accepted. I will not reply to
emails of the type ``my internet connection broke down at
23:57'' or ``my scanner stopped working at 23:58'', or
``my dog ate my laptop charger''.}
\item You are encouraged to collaborate on assignments, but at the level
of discussion only. When writing your solutions, you must do so
in your own words.
\item Past experience has shown conclusively that those who do not put
adequate effort into the assignments do not learn the material and
have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
\begin{itemize}
\item You must justify your answers.
\item The answers should be concise, clear and neat.
\item When presenting proofs, every step should be justified.
\end{itemize}
\end{itemize}
\begin{center}
\hfill\shadowbox{
\begin{minipage}{.90\linewidth}
{\textsf{Some useful formulas:
\begin{enumerate}
\item for any real number $x>0$, $x = 2^{\log x}$.
\item for any real number $x \neq 1$ and any integer $k \geq 1$,
\[ 1 + x + x^2 + \cdots + x^{k-1} = \frac{x^k - 1}{x-1} .
\]
\end{enumerate}
}}
\end{minipage}
}
\end{center}
\newpage
\begin{question}
Write your name and student number.
\end{question}
\begin{question}
Solve the following recurrences using the unfolding method we have seen
in class. In each case, give the final answer using Big-O notation.
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.1)}
\[ T(n) = \left\{ \begin{array}{ll}
1 & \mbox{if $n=1$,} \\
1 + 2 \cdot T(n/3) & \mbox{if $n \geq 3$.}
\end{array}
\right.
\]
You may assume that $n$ is a power of $3$.
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.2)}
\[ T(n) = \left\{ \begin{array}{ll}
1 & \mbox{if $n=1$,} \\
1 + 2 \cdot T(n-1) & \mbox{if $n \geq 2$.}
\end{array}
\right.
\]
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.3)}
\[ T(n) = \left\{ \begin{array}{ll}
1 & \mbox{if $n=2$,} \\
1 + T(\sqrt{n}) & \mbox{if $n \geq 4$.}
\end{array}
\right.
\]
You may assume that $n$ is a power of a power of $2$, so that
$\log\log n$ is an integer.
\end{question}
\begin{question}
In class, we have seen a fast algorithm that computes the product of
two large integers. You may think that squaring an integer is
``easier'' than multiplying two integers. After all, for squaring, you
get one input integer $x$, and have to multiply it by itself, whereas for
multiplication, you have to compute the product of two input integers
$x$ and $y$. In this question, you will show that this is not the
case: The time complexity of multiplication is the same (except for
constant factors) as that of squaring.
\begin{enumerate}
\item You are given an algorithm $\mathcal{A}$ that takes as input an
integer $x \geq 1$, written in binary, and returns the integer $x^2$.
We denote the running time (i.e., the number of bit operations) of
algorithm $\mathcal{A}$ by $S(n)$, where $n$ is the number of bits in
the binary representation of $x$.
\item You learned in elementary school that, given two integers
$x \geq 1$ and $y \geq 1$, both written in binary and both having $n$
bits, their sum $x+y$ and difference $x-y$ can be computed in $O(n)$
time.
\item Given an integer $x \geq 2$, written in binary, and given an
integer $k \geq 1$, such that $x$ is a multiple of $2^k$, we can
compute $x / 2^k$ in $O(k)$ time, by just removing the rightmost
$k$ bits from the binary representation of $x$.
\end{enumerate}
Describe (in plain English or pseudocode), an algorithm $\mathcal{B}$
that takes as input two $n$-bit integers $x$ and $y$, and returns the
product $xy$. Your algorithm $\mathcal{B}$ must use algorithm
$\mathcal{A}$ as a subroutine, as well as the results in 2.\ and 3.\
above, and its running time must be $O(S(n+1))$.
It is easy to come up with an algorithm $\mathcal{B}$ that calls
$\mathcal{A}$ three times. You will get more marks if your algorithm
$\mathcal{B}$ calls $\mathcal{A}$ only twice.
\emph{Hint:} $(x+y)^2$.
\end{question}
\begin{question}
Consider the following recursive algorithm $\APPLE(n)$, which takes as
input an integer $n \geq 1$:
\begin{quote}
\begin{tabbing}
{\bf Algorithm} $\APPLE(n)$: \\
{\bf if} $n=1$ \\
{\bf then} sing ``an apple a day keeps the doctor away'' \\
{\bf else} \= eat one apple; \\
\> choose an arbitrary integer $m$ with $1 \leq m \leq n-1$;
\\
\> $\APPLE(m)$; \\
\> $\APPLE(n-m)$ \\
{\bf endif}
\end{tabbing}
\end{quote}
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.1)}
Explain why, for any integer $n \geq 1$, algorithm $\APPLE(n)$ terminates.
\vspace{0.5em}
\noindent
{\bf (\arabic{ques}.2)}
Let $A(n)$ be the number of apples that you eat when running algorithm
$\APPLE(n)$. Determine the exact value of $A(n)$.
\end{question}
\begin{question}
Let $S$ be a set of $n$ points in the plane. Each point $p$ of $S$ is
given by its $x$- and $y$-coordinates $p_x$ and $p_y$, respectively.
A point $p$ of $S$ is called \emph{maximal} in $S$, if there is no
point in $S$ that is to the north-east of $p$, i.e.,
\[ \{ q \in S \setminus \{ p \} : q_x \geq p_x \mbox{ and }
q_y \geq p_y \}
= \emptyset .
\]
See Figure~\ref{max} for an example. Observe that, in general, there
is more than one maximal element in $S$.
\begin{figure}[t]
\centering
\begin{picture}(50,45)
\put(9,44){$\bullet$}
\put(24,29){$\bullet$}
\put(29,19){$\bullet$}
\put(39,14){$\bullet$}
\put(49,9){$\bullet$}
\put(15,25){$\cdot$}
\put(10,10){$\cdot$}
\put(20,15){$\cdot$}
\put(27,12){$\cdot$}
\put(35,8){$\cdot$}
\end{picture}
\caption{\sl The $\bullet$-points are maximal; the
$\cdot$-points are not maximal.}
\label{max}
\end{figure}
Give a \emph{divide-and-conquer}\footnote{Your algorithm must use
divide-and-conquer} algorithm (in plain English or
pseudocode) that computes all maximal elements in $S$. The running time
of your algorithm must be $O(n \log n)$. Explain why the running time
of your algorithm is $O(n \log n)$ (you may use the Master Theorem).
\emph{Hint:} At the start of the algorithm, sort the points of $S$
from left to right. Use this ordering to divide the input set into two
subsets. You don't have to give pseudocode for the sorting step.
To avoid special cases, you may assume that no two points in $S$ have
the same $x$-coordinate, and no two points in $S$ have the same
$y$-coordinate.
\end{question}
\begin{question}
\emph{(Binary search in an infinite array)}
Let $A[1 \ldots]$ be an infinite array of real numbers such that
\[ 0 = A[1] < A[2] < A[3] < \ldots ,
\]
and let $x$ be a positive real number.
In this question, you are asked to describe (in plain English or
pseudocode) an algorithm that decides whether or not $x$ occurs in $A$.
Let $n$ be the index such that $A[n] \leq x < A[n+1]$. Hence, if
$x$ occurs in $A$, then $x=A[n]$; if $x$ does not occur in $A$,
then $A[n] < x < A[n+1]$. The running time of your algorithm must
be $O(\log n)$. Keep in mind that the input consists \emph{only} of
the array $A$ and the real number $x$; the index $n$ is \emph{not}
part of the input. In other words, at the start of the algorithm,
you \emph{do not know} the value of $n$.
You are allowed to use the binary search algorithm as a subroutine,
and you may use the fact that this algorithm has a logarithmic running
time.
Explain why the running time of your algorithm is $O(\log n)$
\emph{Hint:} In $O(\log n)$ time, compute an index $h$ that is not
``too large'' and for which $A[h] > x$. (You may even show that
such an index can be computed in $O(\log\log n)$ time, but the
rest of the algorithm will still take $O(\log n)$ time.)
\end{question}
\begin{question}
Let $A[1 \ldots n]$ be an array containing numbers in sorted order; you
may assume that all these numbers are distinct. The following algorithm
is a randomized version of the binary search algorithm. The input
consists of the array $A$, its size $n$, and a number $x$. If $x$
is in the array, then the algorithm returns the index $p$ such that
$A[p]=x$. Otherwise, the algorithm returns ``not present''.
\begin{quote}
\begin{tabbing}
{\bf Algorithm} $\RBS(A,n,x)$: \\
$\ell = 1$; $r = n$; \\
{\bf while} $\ell \leq r$ \\
{\bf do} \= $p=$ uniformly random element in
$\{\ell,\ell+1,\ldots,r\}$; \\
\> {\bf if} $A[p] {\bf then} $\ell = p+1$ \\
\> {\bf else} \= {\bf if} $A[p]>x$ \\
\> \> {\bf then} $r=p-1$ \\
\> \> {\bf else} return $p$ \\
\> \> {\bf endif} \\
\> {\bf endif} \\
{\bf endwhile}; \\
return ``not present''
\end{tabbing}
\end{quote}
Let $T$ be the running time of this algorithm. Note that $T$ is a random
variable. Prove that the expected value of $T$ is $O(\log n)$.
\end{question}
\end{document}