\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools}
\usetikzlibrary{shapes,chains,positioning}
\usepackage[pdftitle={CS 341 Assignment 1},%
pdfsubject={University of Waterloo, CS 341, Winter 2025},%
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{Armin Jamshidpey, Mark Petrick, Collin Roberts \\Copyright $\copyright$ 2025 Distribution (except by the authors) is prohibited. \\ ~\\
Due Date: Friday, January 24 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))$.
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 relations using 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).
    \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 use the Master Theorem to verify your result.
\begin{itemize}
\part{a} You may assume that $n$ is a power of 3.
$$
T (n) = \left\{
\begin{array}{ll}
4 ,& n = 1, \\
5 T(n/3) + n \sqrt{n}, & n > 1. 
\end{array}
\right.
$$

\part{b} You don't have to show all nodes on the third level but show enough that we know what you are doing.
$$
T (n) = 
\left\{
\begin{array}{ll}
2 ,& n \leq 1, \\
6T(\frac{3}{7} n) + n^2, & n > 1. 
\end{array}
\right.
$$

\end{itemize}




%%%%%%%%%%   Q3
\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}

%%%%%%%%%% Q4
\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.

\end{document}
