% -*- compile-command: "rubber -d --unsafe hw-00-background.tex" -*-
\documentclass[10pt]{tufte-handout}
\usepackage[num=0,date={August 28},topic=Concept\ review]{algorithms-hw}
\usepackage{mdframed}
\newcommand{\mymin}{\ensuremath{\mbox{\sc FindMin}}\xspace}
\newcommand{\ms}{\ensuremath{\mbox{\sc Mergesort}}\xspace}
\newcommand{\qs}{\ensuremath{\mbox{\sc Quicksort}}\xspace}
\begin{document}
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.
\begin{mdframed}
\begin{center}
\textbf{Start early!} \bigskip
\textbf{Ask for help} when you get stuck!
\bigskip
\textbf{Work together}, but remember to write up \textbf{your own
solutions}. \bigskip
\textbf{Have fun!}
\end{center}
\end{mdframed}
\marginnote[-1in]{I \textbf{expect} you to ask me for help on homework
assignments in this class. If you never ask for any help, you are
either very smart or very foolish.}
\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}
\marginnote{\textbf{Note}: students coming out of data structures
often think that big-$O$ is specifically about measuring
\emph{how long} algorithms take, but it is not. Big-$O$ is a
tool for measuring the rate of growth of one thing relative to
another. We often do use it measure the rate of growth of the
time needed to run an algorithm relative to the size of the
input, but we can use it to measure rates of growth of other
things as well, such as the amount of memory used. Therefore,
you should not assume that these are asking about \emph{time}
unless they explicitly say so. For example, part (a) is asking
\emph{how many leaves} there are in a tree with a depth of $n$,
that is, how fast does the number of leaves grow relative to the
depth? It is not asking \emph{how long} it would take to find
those leaves.} (smallest) upper bound from this list:
$O(1), 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 time needed to sort a list of $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$ in binary
\item time needed to find the closest pair of points among $n$ points
in Euclidean space by simply listing all the pairs
\item time needed to insert $n$ items into a binary heap
\item time needed to find the second largest number in a
\emph{sorted} list of $n$ distinct numbers
\item time needed to find the second largest number in an \emph{unsorted} list
of $n$ distinct numbers
\end{enumerate}
\item Let $p_n$ be defined for all $n \geq 0$ by \marginnote{If you
need a refresher on recursion and induction, there are a lot of
resources posted on the course website!}
\begin{align*}
p_0 &= 0 \\
p_n &= 2p_{n-1} + 1 && (n > 0)
\end{align*}
State and prove a closed formula for $p_n$.
\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 0 \text{ to } n-1$}
\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 should 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.}
\end{enumerate}
\end{document}