\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{fancybox}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}

\newcommand{\Value}{\mathord{\it value}}


%%%%%%%%%%%%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:} Thursday February 1, 23:59.

\vspace{0.5em}

\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
      Brightspace.

\begin{center}
\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}
\shadowbox{
  \begin{minipage}{.90\linewidth}
    {\textsf{Some useful facts:
      \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} . 
               \]
         \item For any real number $0 < \alpha < 1$, 
               \[ \sum_{i=0}^{\infty} \alpha^i = \frac{1}{1-\alpha} . 
               \] 
      \end{enumerate}
      }}
  \end{minipage}
}
\end{center}

\newpage 

\begin{question}
Write your name and student number.
\end{question}

\begin{question} 
Consider the following recurrence, where $n$ is a power of $8$: 
\[ T(n) = \left\{ \begin{array}{ll} 
                    1 & \mbox{if $n=1$,} \\ 
                    n + 64 \cdot T(n/8) & \mbox{if $n \geq 8$.} 
                  \end{array} 
          \right. 
\]

\begin{itemize} 
\item Solve this recurrence using the \emph{unfolding method}. 
Give the final answer using Big-O notation.  
\item Solve this recurrence using the \emph{Master Theorem}. 
\end{itemize} 
\end{question} 

\begin{question} 
Professor Justin Bieber has observed that only five multiplications 
are needed to compute the square of a $2 \times 2$ matrix: 
\[ 
\left( \begin{array}{cc} 
         a & b \\ 
         c & d 
       \end{array} 
\right) 
\left( \begin{array}{cc} 
         a & b \\ 
         c & d 
       \end{array} 
\right) 
= 
\left( \begin{array}{cc} 
         a^2 + bc & b(a+d) \\ 
         c(a+d) & bc + d^2 
       \end{array} 
\right) 
\]
Professor Bieber remembers Strassen's algorithm from COMP 3804. Based 
on this, he claims that, for any given $n \times n$ matrix $A$, the 
matrix $A^2 = AA$ can be computed by a divide-and-conquer algorithm that 
makes five recursive calls, resulting in a running time of 
$O(n^{\log 5})$. 

Is Professor Bieber's claim correct? As always, justify your answer.  
\end{question} 

\begin{question} 
You are given an array $A[1 \ldots n]$ of $n$ numbers. Describe a 
divide-and-conquer algorithm that returns, in $O(n \log n)$ time, 
the value 
\[ \max \{ A[j]-A[i] : 1 \leq i < j \leq n \} . 
\] 
You may describe your algorithm in plain English or in pseudocode. 
Justify the correctness of your algorithm and explain why the running 
time is $O(n \log n)$. You may use any result that was proven in class. 
\end{question}

\begin{question}
You are given a complete binary tree (i.e., all leaves are at the same 
level and the bottom level is full). The levels are numbered 
$0,1,2,\ldots,d-1$ and the number $n$ of nodes satisfies $n=2^d-1$. 
Each node $u$ in this tree stores an integer $\Value(u)$.  

\begin{center}
     \includegraphics[scale=0.7]{tree}
\end{center}

A node $u$ is called a \emph{local minimum} if $\Value(u)$ is less than 
or equal to the values in its neighboring nodes. In the example above, 
all local minima are colored red. 

Describe a recursive algorithm that returns, in $O(\log n)$ time, a 
local minimum in this tree. 

You may describe your algorithm in plain English or in pseudocode. 
Justify the correctness of your algorithm and explain why the running 
time is $O(\log n)$. You may use any result that was proven in class. 

\end{question}

\begin{question}
You are given a \emph{sorted} array $A[1 \ldots n]$ of $n$ 
\emph{distinct} \emph{integers}. Describe a recursive algorithm that 
decides, in $O(\log n)$ time, if there is an index $i$ such that 
$A[i]=i$. If such an index exists, the algorithm returns one such 
index. Otherwise, the algorithm returns ``No''.

You may describe your algorithm in plain English or in pseudocode. 
Justify the correctness of your algorithm and explain why the running 
time is $O(\log n)$. You may use any result that was proven in class. 
\end{question}

\begin{question}
Let $\mathcal{A}$ be the fastest algorithm that takes as input 
two $n$-bit integers $x$ and $y$, and returns the product $xy$. 
Let $T(n)$ be the running time (in terms of bit-operations) of this 
algorithm. 

Let $\mathcal{A}'$ be the fastest algorithm that takes as input 
one $n$-bit integer $x$, and returns the square $x^2$. 
Let $T'(n)$ be the running time (in terms of bit-operations) of this 
algorithm. 

\begin{itemize} 
\item Explain, in at most two sentences, why $T'(n) = O(T(n))$. 
\item Professor Taylor Swift claims that $T'(n) = o(T(n))$, i.e., $T'(n)$ 
is asymptotically smaller than $T(n)$. Her reasoning is that the input 
to algorithm $\mathcal{A}'$ is just one integer, whereas the input to  
algorithm $\mathcal{A}$ consists of two integers. 

Is Professor Swift's claim correct? As always, justify your answer.  

\noindent \emph{Hint:} $(x+y)^2$.  
\end{itemize} 
\end{question}

\end{document} 
