% -*- compile-command: "pdflatex hw-00-background.tex" -*-
\documentclass[10pt]{tufte-handout}
\usepackage[num=0,time=1:00pm,dow=Tuesday,date={September 3},topic=Background]{algorithms-hw}
\newcommand{\mymin}{\ensuremath{\mbox{\sc FindMin}}\xspace}
\newcommand{\ms}{\ensuremath{\mbox{\sc Mergesort}}\xspace}
\newcommand{\qs}{\ensuremath{\mbox{\sc Quicksort}}\xspace}
\begin{document}
To get full credit for this homework assignment, it must be completed,
\marginnote{In theory, you should know the things on this assignment
from previous classes (such as Data Structures and Discrete Math).
However, in my experience, very few students remember everything
here, and that's OK. Use this assignment as an opportunity to help
you figure out some things you should review.} but it will
\emph{not} be graded for correctness (unlike future homework
assignments). Please answer the questions in simple, concise prose and
when appropriate simple, concise pseudocode.
\begin{enumerate}
\item How many times do you have to repeatedly halve $32$ in order to
reach $1$? What about $8192$? Consider the function which given an
input $n$, outputs the number of times $n$ can be repeatedly
halved before falling below $1$. What is the common mathematical
name for this function?
\item For each of the following, answer with the \textbf{best}
(smallest) upper bound from this list: $O(\log n)$, $O(n)$, $O(n
\log n)$, $O(n^2)$, $O(2^n)$. Give a \textbf{brief justification}
for each.
\begin{enumerate}[label=(\alph*)]
\item number of leaves in a depth-$n$ balanced binary tree
\item depth of an $n$-node balanced binary tree
\item number of edges in an $n$-node tree
\item worst-case run time to sort $n$ items using merge sort
\item number of distinct subsets of a set of $n$ items
\item number of bits needed to represent the number $n$
\item time to find the closest pair of points among $n$ points
in Euclidean space by simply listing all the pairs
\item time to insert $n$ items into a binary heap
\item time to find the second largest number in a list of $n$
(not necessarily sorted) numbers
\end{enumerate}
\item We will not use the syntax of any particular programming
language in this course to specify algorithms. Instead, we will
use well-written prose and pseudocode---an intuitive set of
instructions that are appropriate to the problem at hand. For
example, Algorithm~\ref{alg:min} below gives some pseudocode for
finding the smallest integer in an array.
\begin{algorithm*}[h]
\caption{$\mymin(A, n)$} \label{alg:min}
\begin{algorithmic}[1]
\Require An array of integers $A$ of length $n \geq 0$. Empty arrays return $+\infty$.
\medskip
\State $m \leftarrow +\infty$
\For{$i \leftarrow 1\mbox{ to } n$}
\State $m \leftarrow \min(m, A[i])$
\EndFor
\State \Return $m$
\end{algorithmic}
\end{algorithm*}
Write some pseudocode to find the smallest integer value in a binary
tree $T$ with left child $T.\mathit{left}$ and right child
$T.\mathit{right}$ and integer value $T.\mathit{value}$. You can
suppose that $T.\mathit{left}$ (respectively $T.\mathit{right}$) is
{\sc null} if it doesn't have a left (respectively right) child.\marginnote[-4em]{Note
you may not assume $T$ is a binary \emph{search} tree; that is, there
need not be any relationship between the value at a node and the
values at its children, so the smallest integer value could be
anywhere in the tree.}
\item Do you have any questions for me? If so, what are they?
\end{enumerate}
\end{document}