Computer Science Homework Template
Autor
Hannah Fink
Letzte Aktualisierung
vor 7 Jahren
Lizenz
LaTeX Project Public License 1.3c
Abstrakt
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}