\documentclass[a4paper,10pt]{article}
\usepackage{latexsym}
\usepackage{ucs}
%\usepackage[utf8x]{inputenc}
\usepackage{fancyhdr}
\usepackage{clrscode}

\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\fancyhead[R]{Algorithms and Data Structures 1 \\
				2011, Assignment 1}
\fancyfoot[C]{}

% Title Page
\title{\bf Assignment 1}
\author{Jonathan Cederberg}

\begin{document}
\section{Asymptotic growth rates (3 pts)}
Rank these functions in order of growth:
\[
\frac n 2 \quad 4^{\lg n} \quad n! \quad \lg n \quad 2^{2^n} \quad (n+1)! \quad
\left(\frac{100}{99} \right)^n \quad n \lg n \quad n^3 \quad 2^n \quad n\cdot
2^n
\]

In other words, you should order the functions in a sequence $g_1, g_2, \ldots,
g_{11}$ such that $g_1 = \mathcal O (g_2), g_2 = \mathcal O (g_3), \ldots,
g_{10} = \mathcal O (g_{11})$. You should also justify each relation by either
referring to well known relations (where ``well known'' means there is a specific
place in the course book that you can refer to) or give a proof.
Chapter 3 in the book provides excellent reference for this exercise.

\textbf{Hint:} Make sure the function is in its simplest form. If not, use the
rewriting rules in the book to make it simpler.

\section{Tradeoffs (3 pts)}
The \proc{Merge-Sort} procedure described in the lectures calls \proc{Merge}
once for each recursive call. Each time memory space of the same size as input
is allocated (the $L$ and $R$ arrays). \proc{Insertion-Sort}, on the other
hand, allocates no extra memory, but is an algorithm with quadratic running
time. For each case below, justify in \emph{at most} three sentences which
algorithm is the asymptotically better one.
\begin{enumerate}
  \item Memory allocation is done in constant time no matter how much memory is
  allocated.
  \item Memory allocation is done in linear time: allocating something of
  size $n$ takes $\mathcal O (n)$. 
  \item Memory allocation is done in quadratic time: allocating something of
  size $n$ takes $\mathcal O (n^2)$.
\end{enumerate}

\section{\proc{Foo}, \proc{Bar} and \proc{Baz} (4 pts)}
Below the procedures \proc{Foo}, \proc{Bar} and \proc{Baz} are given in
pseudocode. For \proc{Foo} and \proc{Bar}, answer the following four questions:
\begin{enumerate}
  \item What does the procedure do?
  \item What is the best case running time?
  \item What is the average case running time?
  \item What is the worst case running time?
\end{enumerate}
Each answer should be justified in one sentence. Answers without justifications
give 0 points.
\begin{codebox}
\Procname{$\proc{Foo}(A)$}
\li $n \gets \mathrm{size}(A)$
\li \For $i \gets 1$ to $\lfloor\frac n 2\rfloor$
\li    \Do \If not $A[i] = A[n-i+1]$
\li       \Then \Return False
       \End
    \End
\li \Return True
\end{codebox}
\begin{codebox}
\Procname{$\proc{Bar}(A, z)$}
\li \Return $\proc{Baz}(A, 1, \mathrm{size}(A), z)$
\end{codebox}
\begin{codebox}
\Procname{$\proc{Baz}(A, x, y, z)$}
\li    \If $x > y$ or $(x=y$ and $A[x] \neq z)$
\li        \Then \Return $-1$
	   \End
\li    $i\gets x + \left\lfloor\frac{y-x} 2\right\rfloor$
       \End
\li    \If $A[i] = z$
\li        \Then \Return $i$
       \End
\li    \If $A[i] > z$
\li        \Then $\proc{Baz}(A, x, i-1, z)$
\li        \Else $\proc{Baz}(A, i+1, y, z)$
\end{codebox}

\textbf{Hint:} Use pen and paper to run the algorithm for a number of inputs, or
even better implement the procedure in some simple programming language.
\end{document}