\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools}
\usetikzlibrary{shapes,chains,positioning,arrows.meta}
\usepackage[pdftitle={CS 341 Assignment 1},%
pdfsubject={University of Waterloo, CS 341, Winter 2026},%
pdfauthor={MP}]{hyperref}
%\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}

\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}

\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS 341 Winter 2025}\\
\vspace{2mm}
{\Large\bf Written Assignment 1}\\
%\vspace{3mm}
\textbf{Elena Grigorescu, Mark Petrick, Luke Schaeffer \\Copyright $\copyright$ 2025 Distribution (except by the authors) is prohibited. \\ ~\\
Due Date: Friday, January 23 at 11:59pm to Crowdmark \\
All work submitted must be the student's own.}
\end{center}
\begin{itemize}
\item Make sure to read the Assignments section on the course webpage for instructions on submission and question expectations (``Instructions for Assignments"):  \\ \url{https://student.cs.uwaterloo.ca/~cs341/#Assignments}
\end{itemize}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode

%%%%%%%%%%%% Q1
\subsection{[12 marks] Asymptotic Notation}

For each pair of functions $f(n)$ and $g(n)$, 
fill in the correct asymptotic notation among $\Theta$,
$o$, and $\omega$ in the statement $f(n)\in$ \verb*| | $(g(n))$.
If none of these are appropriate, state ``None apply".  
Formal proofs are not necessary, but provide brief justifications
for all of your answers.
(The default base in logarithms is 2.)
\begin{enumerate}
\part{a} $f(n)=n^3 (\log n)^2$\ \ vs.\ \  $g(n)=n^2 (\log n)^3$
\part{b} $f(n)=n^{341} + 2024^n$\ \ vs.\ \ $g(n)= n^{240} + 2025^n$
\part{c} $f(n)=3^{\log_9 n}$\ \ vs.\ \ $g(n)=n^{1/4}+\sqrt{n} + \log n$
\part{d} $f(n) = (\log n)^{\log n}$\ \ vs.\ \ $g(n)=n^2$
\part{e} $f(n) =  \sum_{i=0}^n 2^i $\ \ vs.\ \   $g(n) = 3^n$
\part{f} $f(n) = n^3$\ \ vs.\ \   $g(n) = (\lceil {\frac{n}{2}}\rceil - \frac{n}{2}) n^3$
\end{enumerate}



%%%%%%%%%%   Q2

\subsection{[12 marks] Recursion Tree}

Solve the following recurrence relation, use the recursion tree method.  Express your solution in terms of a $\Theta$ bound on $T(n)$.  Show your work clearly.  
\begin{itemize}
    \item Draw the final tree showing at least 4 levels (including the root and leaves). Show the work done at each node (do not simply give a total for the level).
    \item Give a mathematical expression for the sum of work in the recursion tree identifying the work done in the base cases and the recursive cases (leave this as a summation) - an induction proof is not required.
    \item Simplify the expression (show your work) to give a closed form and derive a $\Theta$ bound on $T(n)$.
\end{itemize}
Note: You may assume that $n$ is a power of 3. You may use the Master Theorem to verify your result.

$$
T (n) = \left\{
\begin{array}{ll}
4 ,& n = 1, \\
5 T(n/3) + n \sqrt{n}, & n > 1. 
\end{array}
\right.
$$


%%%%%%%%%%%%% Q3
\subsection{[12 marks] (Lucky) Guess and Check}

Use induction to verify the following recurrence with the corresponding guess: 
\begin{itemize}
\part{a} $T(n)$ = $3T(\left \lfloor{n/3}\right \rfloor)+2n$ for $n>2$ and $T(n)=1$ for $n \leq 2$ \\
Guess: $T(n) \in O(n \log n)$.
\part{b} $T(n)$ = $3T(\left \lfloor{n/3}\right \rfloor)+10$ for $n>2$ and $T(n)=2$ for $n \leq 2$ \\
Guess: $T(n) \in O(n)$
\end{itemize}
Clearly indicate the following components: Basis, Induction Hypothesis, Induction Step and  Concluding Statement. You should also clearly label where you are using the induction hypothesis in the induction step.

\noindent Hint: You may use the fact that $\left \lfloor{n/3}\right \rfloor \leq (n/3)$ to simplify the floors away.



%%%%%%%%%%   Q4
\subsection{[10 marks] Divide and Conquer I}
\begin{itemize}
\part{a} Researchers are often ranked by their $h$-index which is the maximum integer $h$
such that the researcher has at least $h$ papers that have been cited at least $h$ times.
Suppose Professor X has written $n$ papers and paper $i$ has been cited $a_i$ times and
you have the papers sorted with $a_1 > a_2 > \dots > a_n$. Design a $O(\log n)$ time divide-and-conquer algorithm to find Professor X's $h$-index.
\part{b} Suppose you have two sorted arrays $A$ and $B$ each containing $n$ numbers. Design a divide-and-conquer algorithm to find the median of all the 2$n$ numbers in $O(\log n)$ time.
\end{itemize}

%%%%%%%%%% Q5
\subsection{[10 marks] Divide and Conquer II}
Suppose you are given a set $S$ of $n$ points in the plane where each point is labelled either ``red" or ``blue".
We want to count the number of pairs $(r, b)$ where $r$ is a red point in S
and $b$ is a blue point in $S$, such that $r$ dominates $b$. Here, we say that $r$ dominates $b$ if $r$ has larger x-coordinate and larger y-coordinate than $b$. 
Design a divide-and-conquer algorithm that divides the points in half using the median x-coordinate and solves this problem in $O(n \log n)$ time. Analyze the runtime of your algorithm.

\begin{figure}
    \begin{center}
    \Large
	\begin{tikzpicture}[scale=1.4,>={Stealth[length=4mm, width=3mm]}]
		\coordinate (SW) at (-0.4,-0.4);
		\coordinate (NE) at (6,4.5);

		\coordinate (A) at (1,3.8);
		\coordinate (B) at (2,2.2);
		\coordinate (C) at (3,0.8);
		\coordinate (D) at (4,1.5);
		\coordinate (E) at (5,3);
		
		% Light grid
		\draw[step=0.5cm, gray!30, very thin] (SW) grid (NE);
		
		% Axes
		\draw[->, thick] (-.4,0) -- (6.4,0) node[right] {$x$};
		\draw[->, thick] (0,-.4) -- (0,4.9) node[above] {$y$};

		% Dominated regions
		\fill[black, opacity=0.1] (-0.2,-0.2) rectangle (A);
		\fill[black, opacity=0.1] (-0.2,-0.2) rectangle (D);
		\fill[black, opacity=0.1] (-0.2,-0.2) rectangle (E);
				
		% Points
		\filldraw[red] (A) circle (2pt) node[above right] {$A$};
		\filldraw[blue] (B) circle (2pt) node[below left] {$B$};
		\filldraw[blue] (C) circle (2pt) node[below left] {$C$};
		\filldraw[red] (D) circle (2pt) node[above right] {$D$};
		\filldraw[red] (E) circle (2pt) node[above right] {$E$};
        
	\end{tikzpicture}
    \end{center}
    \caption{An instance with red points $\{ A,D,E \}$ and blue points $\{ B,C \}$ where $E$ dominates $B$ and $C$ (and $D$, technically, but $D$ is red), $D$ dominates $C$, and $A$ dominates nothing.}
\end{figure}

\end{document}