% -*- compile-command: "pdflatex hw.0.tex" -*-
\documentclass[11pt]{article}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace,algorithm,algorithmic}
\usepackage[left=1in,top=1in,right=1in,bottom=1in]{geometry}

\pagestyle{fancy}


% Comment out for single spacing
%\baselineskip 20pt


\lhead{CSCI 280: Algorithms -- Spring 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 0}
\rfoot{Due: 4:00pm, Friday, January 20}
\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
%\renewcommand{\footwidth}{\textwidth}
%\addtolength{\headwidth}{\marginparwidth}
%\addtolength{\headwidth}{\marginparsep}
\renewcommand{\footrulewidth}{0.4pt}


\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,
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{itemize}

  \item What is your expected graduation year?

  \item What are your (intended) major(s) and minor(s)?

  \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)$.
    \begin{itemize}
  	\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{itemize}

  \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
\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.

  \item Do you have any questions for me?  If so, what are they?

\end{itemize}

\end{document}
