cs341a1/q2/q2.tex

\documentclass[11pt]{article}
\usepackage{amsthm,amsmath,amsfonts,amssymb}
\usepackage[ruled,noline,noend]{algorithm2e}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}

%%% Update the following commands with your name, ID, and acknowledgments.
\newcommand{\YourName}{REPLACE WITH YOUR NAME}
\newcommand{\YourStudentID}{REPLACE WITH ID NUMBER}
\newcommand{\YourAck}{REPLACE this text with a full acknowledgement of all sources (people you discussed the question with and/or online/text sources you consulted) used while completing this question. If you completed the question without consulting any sources, say so here explicitly.}


\newenvironment{solution}{\paragraph{Solution.}}{}


\title{
\vspace{-0.8in} \normalsize
\begin{flushright} \YourName \\ \YourStudentID \end{flushright}
\rule{\textwidth}{.5pt}\\[0.4cm] \huge Assignment 1: Question 2 \\
\rule{\textwidth}{2pt}
\vspace{-1in}
}
\date{}

\begin{document}
\maketitle
\paragraph{Acknowledgments.} \YourAck



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Solving recurrences}

Solve the following recurrence relations to obtain a closed-form big-$\Theta$ expression for $T(n)$.
In each question, assume $T(c)$ is bounded by a constant for any small constant $c$.

\begin{enumerate}[(a)]
\item $T(n) = 9\,T(\frac{n}{3}) + n^2$

\begin{solution}
(ENTER YOUR SOLUTION HERE.)
\end{solution}

\item $T(n) = 4\,T(\frac{n}{4}) + n \log n$

\begin{solution}
(ENTER YOUR SOLUTION HERE.)
\end{solution}

\item $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + n$

\begin{solution}
(ENTER YOUR SOLUTION HERE.)
\end{solution}

\item $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n$ \\
\emph{Hint.} The correct expression is somewhere between $\Omega(n)$ and $O(n \log n)$.

\begin{solution}
(ENTER YOUR SOLUTION HERE.)
\end{solution}

\end{enumerate}

\end{document}