% -*- 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}
