% -*- 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 2016}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 0}
\rfoot{Due: 4:00pm, Friday, January 22}
\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}

This homework will not be graded and it will not count as one of the
graded assignments.  Completion, however, is mandatory.  Please answer
the questions in simple, concise prose and when appropriate simple,
concise pseudocode.  Please do not use any outside resources,
including your textbook, when answering these questions.  Don't worry
if you are uncertain about an answer or if you do not know an answer
or if something looks unfamiliar.  Just be honest.  It will be fine.
I promise.

\begin{itemize}

  \item Please tell me your (intended) major(s) and minor(s).

  \item Seriously, what do you think of when you see the words {\em
      Algorithms and Problem Solving Paradigms}?

  \item What was your favorite part of CSCI 150 or CSCI 151?  Why?

  \item For each of the following, answer with the tightest 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 enumeration
	\item time to insert $n$ items into a binary heap
	\item time to find the second largest number in a set of $n$ (not necessarily sorted) numbers
  \end{itemize}

  \item How many times can you repeatedly halve 32 {\em before} falling below 1?  What is the common mathematical name for this operation?

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