Computer Science Homework Template
Författare
Hannah Fink
Last Updated
5 years ago
Licens
LaTeX Project Public License 1.3c
Sammanfattning
CS 405 Analysis of Algorithms homework template.
CS 405 Analysis of Algorithms homework template.
\documentclass{article}%
\usepackage{amsmath}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
%-------------------------------------------
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\setlength{\textwidth}{7.0in}
\setlength{\oddsidemargin}{-0.35in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.0in}
\setlength{\parindent}{0.3in}
\begin{document}
\begin{flushright}
\textbf{Jane Doe \\
MONTH DAY, 2017}
\end{flushright}
\begin{center}
\textbf{CS 405: Algorithm Analysis II \\
Homework NUM: TITLE} \\
\end{center}
Each of the exercises below involves a choice among the master theorem templates discussed in lecture.
For each, indicate which case applies and specify the asymptotic growth class of the function. If no
case applies, simply state that fact; you are not required to attempt a solution when no master theorem case
applies.
\begin{enumerate}
\item $T(n) = 2 T(\lfloor n/4 \rfloor) + n^{1/2}$.
\item $T(n) = 3 T(\lfloor n/2 \rfloor) + n \lg n$.
\item $T(n) = 5 T(\lfloor n/5 \rfloor) + \frac{n}{\lg n}$.
\item $T(n) = 4 T(\lfloor n/2 \rfloor) + n^2 \sqrt{n}$.
\item $T(n) = 2 T(\lfloor n/2 \rfloor) + n \lg n$.
\end{enumerate}
\section*{Solutions.}
$a = 3, b = 2$ implies a reference function $g(n) = n^{\log_2 3}$. Converting as follows,
\begin{eqnarray*}
y & = & \log_2 3 \\
2^y & = & 3 \\
y \ln 2 & = & \ln 3 \\
y & = & \frac{\ln 3}{\ln 2} = 1.585,
\end{eqnarray*}
we have $g(n) = n^{1.585}$. The ``glue'' function is $f(n) = n \lg n$. Let $g_\epsilon (n) = n^{1.585 - \epsilon}$, for
$0 < \epsilon < 0.5$. Since
\begin{eqnarray*}
\frac{f(n)}{g_\epsilon (n)} & = & \frac{n \lg n}{n^{1.585 - \epsilon}} = \frac{\lg n}{n^{0.585 - \epsilon}} \\
& \leq & \frac{\lg n}{n^{0.085}} \rightarrow 0
\end{eqnarray*}
as $n \rightarrow \infty$, we have $f(n) = o(g_\epsilon (n))$, which implies $f(n) = O(g_\epsilon (n))$ and allows case (1) of the
master template. Therefore $T(n) = \Theta(g(n)) = \Theta(n^{1.585})$.
\vspace*{0.5in}
\noindent Answers to incidental LaTeX question may be found at:
\begin{verbatim}
http://www.tug.org/begin.html
\end{verbatim}
\newpage
NEW PAGE!!!
\end{document}