% -*- compile-command: "./build.sh" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[outputdir=diagrams, extension=pgf, backend=pgf, input]{diagrams-latex}
\usepackage{pgf}
\usepackage[num=2,date=September\ 11,topic=Asymptotic\ analysis]{algorithms-hw}
\begin{document}
\coversheet
\begin{question}[K\&T 2.2, 5 points] \label{q:running} Suppose you have
algorithms with the six running times listed below. (Assume these
are the \emph{exact} number of operations performed as a function of
the input size $n$.) Suppose you have a computer that can perform
$10^{10}$ operations per second, and you need to compute a result in
at most an hour of computation. For each of the algorithms, what is
the largest input size $n$ for which you would be able to get the
result within an hour? For answers smaller than $10^{10}$, give
your answer as an exact integer; for larger answers you may provide
an approximation.
\marginnote[-4em]{\emph{\ref{q:running}}\quad\qrcode{Most\ of\ these\
can\ be\ solved\ analytically,\ but\ for\ at\ least\ one\ you\ may\ need\ to\
resort\ to\ numeric\ methods\ (e.g.\ use\ Wolfram\ Alpha\ or\ write\
a\ bit\ of\ code\ yourself).}}
\begin{enumerate}
\item $n^2$
\item $n^3$
\item $100n^2$
\item $n \log_2 n$
\item $2^n$
\item $2^{2^n}$
\item $n!$
\end{enumerate}
\end{question}
In addition to $O$, $\Theta$, and $\Omega$, we will also sometimes use
the notation $o(g(n))$ (little-o) to mean that a function is $O(g(n))$
but \emph{not} $\Theta(g(n))$. So, if $\lim_{n \to \infty} T(n)/g(n)
= 0$, then $T(n)$ is $o(g(n))$. Intuitively, if big-O is like
``less than or equal to'', little-o is like ``less than''; if $f(n)$
is $o(g(n))$ then $f$ ``grows strictly more slowly than'' $g$.
\begin{question}[Some asymptotic properties, 5 points] \label{q:props}
\mbox{}
\begin{enumerate}[label=(\alph*)]
\item Show that $n^j$ is $o(n^k)$ whenever $j < k$.
\item Prove that $\log_a n$ is $\Theta(\log_b n)$ for any positive
integer bases $a,b > 1$. \marginnote{\emph{Hint}: recall, or look
up, the change-of-base formula for logarithms.} Conclude that
we are justified in writing simply $\Theta(\log n)$ without caring
about the base of the logarithm.
\item Prove that $n^k$ is $o(b^n)$ for any positive integer $k$ and
any real number $b > 1$. For example, $n^{295}$ is $o(1.0001^n)$.
\emph{In the long run}, any polynomial function grows more slowly
than any exponential function! \marginnote{\emph{Hint}: use
L'H\^opital's rule $k$ times. Recall that the derivative of
$b^n$ with respect to $n$ is $b^n \ln b$.}
\end{enumerate}
\end{question}
\newpage
\begin{question}[K\&T 2.3, 5 points]
Take the following list of functions and arrange them in ascending
order of asymptotic growth rate. That is, if function $g(n)$ immediately
follows function $f(n)$ in your list, then it should be the case
that $f(n)$ is $O(g(n))$. Please prove/justify your claims.
\begin{enumerate}
\item $f_{1}(n) = n^{2.5}$
\item $f_{2}(n) = \sqrt{2n}$
\item $f_{3}(n) = n + 10$
\item $f_{4}(n) = 10^n$
\item $f_{5}(n) = 100^n$
\item $f_{6}(n) = n^2 \log n$
\end{enumerate}
\end{question}
\begin{question}[15 points] \label{q:theta} Characterize the asymptotic behavior
of each of the following in terms of $n$, using $\Theta$. \textbf{Give
a brief justification for each answer.} For items asking for
the time needed to perform some operation or solve some problem, you
should describe the \emph{worst case} running time of the \emph{best
possible} algorithm.\marginnote[-0.2in]{\textbf{Please come ask
for help} if you are unsure about any of these!}
\begin{enumerate}[label=(\alph*)]
\item $1 + 2 + 3 + 4 + \dots + n$
\item Average number of array lookups needed to find a given element
in a sorted array of length $n$.
\item Number of two-element subsets of a set of size $n$.
\item $1 + 2 + 4 + 8 + \dots + 2^n$
\item Total number of nodes in a complete binary tree with $n$
leaves. \label{qi:binary}
\begin{marginfigure}[-8em]
\begin{center}
\begin{diagram}[width=100]
import Diagrams.Prelude hiding (Empty)
import Diagrams.TwoD.Layout.Tree
import Data.Maybe
dia = symmLayoutBin' opts (fullTree 4)
# fromJust
# renderTree (const (circle 0.1 # fc black)) (~~)
===
strutY 1
===
text "$\\underbrace{\\phantom{XXXXXXXXX}}_n$"
where
opts = def
fullTree 0 = Empty
fullTree n = BNode () (fullTree (n-1)) (fullTree (n-1))
\end{diagram}
\vspace{2em}
\emph{\ref{q:theta}\ref{qi:binary}}
\end{center}
\end{marginfigure}
\item Number of edges in a graph with $n$ nodes, where every node is
connected to every other node. \label{qi:complete}
\begin{marginfigure}
\begin{center}
\begin{diagram}[width=70]
import Diagrams.Prelude hiding (Empty)
tournament :: Int -> Diagram B
tournament n = atPoints (trailVertices $ regPoly n 1) (map node [1..n]) -- $
# applyAll [connect j k | j <- [1 .. n-1], k <- [j+1 .. n]]
where
node n = circle 0.07 # fc black # named n
dia :: Diagram B
dia = tournament 7
\end{diagram}
\emph{\ref{q:theta}\ref{qi:complete}}
\end{center}
\end{marginfigure}
\item Number of different ways to arrange $n$ people in a line.
\item Average number of steps needed to find a given element in a
sorted linked list of length $n$.
\item Biggest integer that can be represented with $n$ bits.
\item Worst-case number of swaps needed to sort an array of length $n$
if you are only allowed to swap adjacent elements.
\item \label{qi:check} Worst-case number of steps needed to check
whether two lists, each containing $n$ integers (not necessarily
sorted), have any element in common.
\marginnote[-4em]{\emph{\ref{q:theta}\ref{qi:check}}\quad\qrcode{Theta(n^2)\
is\ too\ slow!}}
\newpage
\item Number of array lookups performed by this Python code:
\begin{verbatim}
for i in range(0,n):
for j in range (0,i):
sum += array[i][j]
\end{verbatim}
\item Number of addition operations performed by this Java code:
\begin{verbatim}
for (int i = 0; i < n; i += 3) {
sum = sum + i;
}
\end{verbatim}
\item Total number of calls to \texttt{println} performed by this Java code:
\begin{verbatim}
for (int i = 1; i < n; i *= 2) {
for (j = 0; j < 20; j++) {
System.out.println(i + j);
}
}
\end{verbatim}
\item Total number of calls to \texttt{print} performed by this
Python code:
\begin{verbatim}
def foo(n):
print(n)
if n > 0:
foo(n-1)
foo(n-1)
\end{verbatim}
\end{enumerate}
\end{question}
\begin{question}[K\&T 2.8, 5 points]
You're doing some stress-testing on various models of glass jars to
determine the height from which they can be dropped and still not
break. The setup for this experiment, on a particular type of jar,
is as follows. You have a ladder with $n$ rungs, and you want to
find the highest rung from which you can drop a copy of the jar and
not have it break. We call this the \emph{highest safe rung}.
It might be natural to try binary search: drop a jar from the middle
rung, see if it breaks, and then recursively try from rung $n/4$ or
$3n/4$ depending on the outcome. But this has the drawback that you
could break a lot of jars in finding the answer.
If your primary goal were to conserve jars, on the other hand, you
could try the following strategy. Start by dropping a jar from the
first rung, then the second rung, and so forth, climbing one higher
each time until the jar breaks. In this way, you only need a single
jar---at the moment it breaks, you have the correct answer---but you
may have to drop it $n$ times (rather than $\log n$ times as in the
binary search solution).
So here is the trade-off: it seems you can perform fewer drops if
you're willing to break more jars. To understand better how this
trade-off works at a quantitative level, let's consider how to run
this experiment given a fixed ``budget'' of $k \geq 1$ jars. In
other words, you have to determine the correct answer---the highest
safe rung---and can use at most $k$ jars in doing so.
\begin{enumerate}[label=(\alph*)]
\item Suppose you are given a budget of $k = 2$ jars. Describe a
strategy for finding the highest safe rung that requires you to
drop a jar at most $f(n)$ times, for some function $f(n)$ that
grows slower than linearly. (In other words, $f(n)$ should be
$o(n)$, that is, $\lim_{n \to \infty} f(n)/n = 0$.)
\item Now suppose you have a budget of $k > 2$ jars, for some given
$k$. Describe a strategy for finding the highest safe rung using
at most $k$ jars. If $f_k(n)$ denotes the number of times you
need to drop a jar according to your strategy, then the functions
$f_1, f_2, f_3, \dots$ should have the property that each grows
asymptotically slower than the previous one: $\lim_{n \to \infty}
f_k(n)/f_{k-1}(n) = 0$ for each $k$.
\end{enumerate}
\end{question}
% \begin{question}[Subinterval sums, K\&T 2.6] \label{q:subinterval}
% Consider the following basic problem. You're given an array $A$
% consisting of $n$ integers $A[1], A[2], \dots, A[n]$. You'd like to
% output a two-dimensional $n \times n$ array $B$ in which $B[i,j]$
% (for $i \leq j$) contains the sum of array entries $A[i]$ through
% $A[j]$---that is, the subinterval sum $A[i] + A[i+1] + \dots +
% A[j]$. (The value of array entry $B[i,j]$ is left unspecified
% whenever $i > j$, so it doesn't matter what is output for these
% values.)
% For example, given the array $A = [1,5,7,2]$, the desired output
% $B$ would be \[
% \begin{bmatrix}
% 1 & 6 & 13 & 15 \\
% & 5 & 12 & 14 \\
% & & 7 & 9 \\
% & & & 2
% \end{bmatrix}.
% \]
% (Note this is formulated slightly differently than K\&T 2.6, which
% only requires $B[i,j]$ to be defined when $i < j$, but that is
% silly. The sum $A[i] + A[i+1] + \dots + A[j]$ is perfectly
% well-defined when $i = j$; it is equal to $A[i]$. (For that matter,
% the sum is perfectly well-defined when $i > j$ too (it is $0$), but
% let's ignore that.))
% Here's a simple algorithm to solve this problem.
% \begin{algorithmic}[1]
% \FOR{$i \leftarrow 1 \dots n$}
% \FOR{$j \leftarrow i \dots n$}
% \STATE Add up array entries $A[i]$ through $A[j]$
% \STATE Store the result in $B[i,j]$
% \ENDFOR
% \ENDFOR
% \end{algorithmic}
% Note that $j$ starts at $i$, not at $1$.
% \begin{enumerate}[label=(\alph*)]
% \item For some function $f$ that you should choose, give a bound of
% the form $O(f(n))$ on the running time of this algorithm on an input
% of size $n$ (i.e., a bound on the number of operations performed by
% the
% algorithm). \marginnote{\emph{\ref{q:subinterval}(a)}\quad\qrcode{Don't\
% forget\ to\ include\ the\ time\ needed\ to\ add\ up\ $A[i]$\ through\
% $A[j]$.}}
% \item For this same function $f$, show that the running time of the
% algorithm on an input of size $n$ is also $\Omega(f(n))$. (This
% shows an asymptotically tight bound of $\Theta(f(n))$ on the running
% time.)
% \item Although the algorithm you analyzed in parts (a) and (b) is the
% most natural way to solve the problem---after all, it just iterates
% through the relevant entries of the array $B$, filling in a value
% for each---it contains some highly unnecessary sources of
% inefficiency. Give a different algorithm to solve this problem,
% with an asymptotically better running time. In other words, you
% should design an algorithm with a running time that is $o(f(n))$.
% % Make a practical component to this? Example big enough where
% % the $O(n^2)$ algorithm is OK but $O(n^3)$ takes too long? Maybe
% % have them implement both and see. Give both small and biggish
% % example.
% %
% % S'16 --- decided this was too much work.
% % Could be a fun addition to the assignment in a future offering of
% % the course (perhaps removing something else).
% \end{enumerate}
% \end{question}
% \begin{question} \mbox{}
% \begin{enumerate}[label=(\alph*)]
% \item On a scale of 1 to 10, how difficult was this assignment?
% \item How many hours would you estimate that you spent on it?
% \item Which question(s) did you find most difficult? Why?
% \end{enumerate}
% \end{question}
\end{document}