\documentclass[11pt]{article}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{fullpage}
%\usepackage[]{algorithm2e}
\usepackage[normalem]{ulem}
\usepackage{xcolor}
\usepackage{tcolorbox}
\usepackage{latexsym}              % Additional LaTeX Symbols
\usepackage{amssymb}               % AMS Fonts
\usepackage{enumitem}
\usepackage{pseudocode}
\newcommand{\nats}{\ensuremath{\mathbb N}}
\newcommand{\Real}{\ensuremath{\mathbb R}}
\newcommand{\ind}[1]{\hspace*{#1em}}
\newcommand{\Algorithm}{{\bf Algorithm\ }}
\newcommand{\Subroutine}{{\bf Subroutine\ }}
\newcommand{\Comment}{{\bf Comment\ }}
\newcommand{\Note}{{\bf Note:\ }}
\newcommand{\Assert}{{\bf assert:\ }}
\newcommand{\Input}{{\bf Input:\ }}
\newcommand{\Output}{{\bf Output:\ }}
\newcommand{\Caveat}{{\bf Caveat:\ }}
\newcommand{\Condition}{{\bf Condition:\ }}
\newcommand{\For}{{\bf for\ }}
\newcommand{\From}{{\bf from\ }}
\newcommand{\Downto}{{\bf downto\ }}
\newcommand{\To}{{\bf to\ }}
\newcommand{\By}{{\bf by\ }}
\newcommand{\Do}{{\bf do\ }}
\newcommand{\Od}{{\bf od}}
\newcommand{\While}{{\bf while\ }}
\newcommand{\If}{{\bf if\ }}
\newcommand{\Then}{{\bf then\ }}
\newcommand{\Else}{{\bf else\ }}
\newcommand{\Elif}{{\bf elif\ }}
\newcommand{\Fi}{{\bf fi}}
\newcommand{\myAnd}{{\bf and\ }}
\newcommand{\Or}{{\bf or\ }}
\newcommand{\Break}{{\bf break}}
\newcommand{\Next}{{\bf next}}
\newcommand{\Return}{{\bf return\ }}
\newcommand{\bigO}{{O\tilde{\phantom{\imath}}}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\Q}{\ensuremath{\mathbb Q\mskip1mu}}
\newcommand{\K}{{\mathsf{K}}}
\newcommand{\F}{{\mathsf{F}}}
\newcommand{\R}{{\mathsf{R}}}
\newcommand{\B}{{\mathsf{B}}}
\newcommand{\M}{{\mathsf{M}}}
\newcommand{\MM}{{\mathsf{MM}}}
\newcommand{\remove}[1]{{}}
\newcommand{\ignore}[1]{{}}
\newcommand{\rednote}[1]{{\color{red} #1}}
\newcommand{\bluenote}[1]{{\color{blue} #1}}

% for typesetting code
\definecolor{commentsColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{stringColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{xcolor}
\definecolor{stringColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{commentsColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{listings}
\usepackage{hyperref}
\lstset{
  language=C++,
  columns=fullflexible,
  basicstyle=\ttfamily,
  commentstyle=\mycommentstyle,
  breaklines=true,
  escapechar=\$,
  rulecolor = \color{gray},
  frame=none,
  keywordstyle=\color{blue},
  stringstyle=\color{stringColor},
  commentstyle=\color{commentsColor}\textit,
  numbers = none,
  xleftmargin=0.5in
}
\hypersetup{
  colorlinks,
  linkcolor=blue,
}

\begin{document}

\noindent
{CS 341, Fall 2025 \hfill  T. Brown, É. Schost}

\begin{center}
\large\bf ASSIGNMENT 1
\end{center}

\bigskip
\noindent
DO NOT COPY.  ACKNOWLEDGE YOUR SOURCES.

\medskip
\noindent
Please read \verb|http://www.student.cs.uwaterloo.ca/~cs341| for
general instructions and policies.

{\bf Note:} All logarithms default to base 2 (i.e.,  $\log x$ is defined as $\log_2 x$).
{\bf Note:}  ``Giving'' an algorithm means doing the four parts (i)--(iv) as described on the course web page. 
\bigskip
\noindent



\begin{enumerate}

    \item{[10 marks]} \textbf{Order notation.}

        For each of the following questions, please justify your answers.
        
        \begin{enumerate}
            \item{[3 marks]}
                Give a function that is $o(n^3)$ but $\Omega(n^{3-\epsilon})$ for all $\epsilon > 0$ (and justify this).
                
            \item{[2 marks]}
                Use the limit technique to compare the growth of $1.01^n$ and $n^2$ (and report the relationship in terms of $\omega, \Omega, o, O, \Theta$ as appropriate).

            \item{[3 marks]}
                Suppose $f(n) \in o(g(n))$. Does it follow that $\log(f(n)) \in o(\log(g(n)))$?
            
            \item{[2 marks]}
                Compare the growth of $\log (n!)$ and $n\log n$ (and report their relationship).

        \end{enumerate}



\item{[13 marks + bonus]} \textbf{Recurrence relations.}
In all these questions, if you use the master theorem, you of course don't have to reprove it.
        
\begin{enumerate}
\item{[2 marks]} Consider an $n \times n$ upper triangular matrix $M$, with $1$'s on the diagonal (you can assume that $n$ is  a power of 2). We can write 
\[ M = \begin{bmatrix} A & B \\ 0 & C \end{bmatrix}\]
with $A,B,C$ matrices of size $n/2 \times n/2$. Then, one can verify (you don't have to do it) that the inverse of 
$M$ is 
\[M^{-1} = \begin{bmatrix} A^{-1} & - A^{-1}BC^{-1} \\ 0 & C^{-1} \end{bmatrix}\]
Suppose you use Strassen's algorithm to multiply matrices. Write the recurrence for the cost of inverting $M$, 
and solve it (give a $\Theta$).

\item{[2 marks]} Set $T(n)=3 T(n-4) + 1$ for $n > 3$ and $T(n) = 0$ for $n \le 3$. Give a $\Theta$ bound for $T(n)$, and \textbf{prove inductively} that your bound is correct.

\item{[2 marks]} A well-known algorithm for multiplying polynomials is based on the following recursive approach, for $n$ a power of a power of $2$: do $2\sqrt{n}$ calls in size $\sqrt{n}$ and $n \log(n)$ extra operations. The base case is $n=2$, with $T(2)=0$. 
Give a Theta bound for $T(n)$.


\item{[3 marks + bonus]} Suppose that Algorithm A solves a problem of size $n$ by dividing it into $10$ subproblems of size $n/5$
and $4$ subproblems of size $n/4$, recursively solving each subproblem, and then combining
the solutions in time $n$. Give an $\Omega$ bound and a (not necessarily matching) $O$ bound on its runtime (you will not get any credit for answering $T(n) \in \Omega(n)$).

\noindent{\bf Bonus, worth 3 extra marks:} give and prove a $\Theta$ bound on the runtime. You cannot use any theorem that was not proved in class.

\item{[2 marks]} Set $T(n)=2T(n/2) + n \log^k(n)$ for $n > 1$, $T(1) = 0$, where $k$ is a constant.  Give a Theta bound for $T(n)$. You can assume that $n$ is a power of 2 if you want.

\item{[2 marks]} Let $T(n) = 4T(n/2) + n^{2.5} \log n$, and $T(0) = 0$. Solve using the general master theorem.

\end{enumerate}

\medskip

\item{[10 marks]} \textbf{Divide \& Conquer.}

The number of bits in the binary representation of an integer $a$
is given by
$$
\lg a = \left \{ \begin{array}{ll} 1 & \mbox{if $a=0$;}\\
 1 + \lfloor \log |a|\rfloor, & \mbox{otherwise.} \end{array} \right .
$$
Consider a software library for multi-precision nonnegative integers
(whose type we will call \verb|LongInt|) that includes the following
two functions:
\begin{itemize}
\item
   \verb|LongInt(x)|  --
   takes as input a primitive type integer $x, 0 \leq x  < 2^{64}$, and
   returns a \verb|LongInt| with the value $x$.\\ 
   Run-time: $O(1)$.
\item
   \verb|Mul(A,B)| --
   takes as input two \verb|LongInt|'s and
   returns a \verb|LongInt| with the value $A\times B$. 
\\ Run-time: $O(\max(\lg A,\lg B) \min(\lg A, \lg B)^{\log_2 3 -1})$ (Karatsuba's algorithm)
\end{itemize}
In this question you will consider the problem of
multiplying together $n$ primitive type integers to obtain
a single large integer.

As input you are given an array $a[1\ldots n]$ of length $n \geq
1$, each entry being a primitive integer (e.g., fits into 64 bits).
Your task is to write a procedure that computes the product
of all the integers in $a$ and returns the answer as
a \verb|LongInt|.  Here is one solution that simply accumulates the product:\\

{\tt MultiMul}$(a[1\ldots n],n)$\\
\ind{1} $P := {\tt LongInt}(a[1])$\\
\ind{1} \For $i$ \From  2 \To $n$ \Do\\
\ind{2} $P := {\tt Mul}(P,{\tt LongInt}(a[i]))$\\
\ind{1} \Return $P$

To estimate the run-time of algorithms using the multi-precision
library we sum the cost of the calls to the functions defined above.
Note that operations with primitive types like array indices and
loop variables are assumed to have unit cost.
\begin{enumerate}
\item[(a)] {[2 marks]} Analyse the run-time of procedure \verb|MultiMul|,
that is, derive a tight big-$O$ bound for the run-time in terms of $n$.

\item[(b)] {[8 marks]} Design and analyse a divide and conquer
algorithm that does the same job
as \verb|MultiMul| but with run-time $O(n^{\log_2 3})$.

\end{enumerate}

\end{enumerate}

\end{document}