\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{amsmath}


\begin{document}

\begin{center}
{ \Large \bf CMPU 241 - Analysis of Algorithms}\\
  {\bf Spring 2020 \\
 Assignment 2\\
 Due: Friday, February 14th at 5pm\\}
  \vspace{.15in}
NAME: (1 point) \underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\\

\end{center}







\begin{enumerate}

\item  (12 points) Give tight asymptotic bounds for $T(n)$ in each of the 
following recurrences.  Use backward substitution, either version of the Master Theorem, Recursion Tree, or 
make a good guess and show that it holds. 
Assume that $T(n)$ is constant for $n \leq 2$.  State your method of solution and {\it if 
you use either version of the Master Theorem, state version of the Master Theorem you are using, and the case the recurrence falls into (Case 1, 2, or 3)}.
Show all your work for full credit.\\

\begin{enumerate}
\item[a.] $T(n) = T(\frac{9n}{10}) + n$\\

\vspace{.75in}

\item[b.] $T(n) = 2T(\frac{n}{4}) + \sqrt{n}$\\

\vspace{.75in}

\item[c.] $T(n) = T(n - 1) +  n$\\

\vspace{.75in}

\item[d.] $T(n) = 3T(\frac{n}{2}) + n$\\

\vspace{.75in}

\item[e.] $T(n) = 6T(\frac{n}{4}) + n^2$\\ 

\vspace{.75in}

\item[f.] $T(n) = 3T(\frac{n}{4}) + nlgn$\\

\end{enumerate}


\vspace{20mm}
\newpage


\item (10 points) Consider the {\sc Selection-Sort} algorithm, given below. Assume the input and output are as specified for the sorting problem on page 16 of our textbook.


\begin{center}
\begin{tabular}{l l}
\multicolumn{2}{l} {{\sc Selection-Sort}(A):}\\
1. & $n = A.$length \\
2. & for $j = 1$ to $n-1$ \\
3. & \hspace{5mm} smallest $= j$ \\
4. & \hspace{5mm} for $i = j + 1$ to $n$ \\
5. & \hspace{10mm} if $A[i] < A[$smallest$]$\\ 
6. & \hspace{15mm} smallest $= i$ \\
7. & \hspace{5mm} exchange $A[j]$ with $A[$smallest$]$\\
\end{tabular}
\end{center}

Consider the following loop invariant of the outer for loop (lines 2 through 7).

\begin{quote} 
The algorithm maintains the loop invariant that at the start of each iteration, the subarray $A[1..j-1]$ consists of the 
$j-1$ smallest elements in the array $A[1..n]$ and the subarray $A[1..j-1]$ is in sorted order.
\end{quote}

 
Show that the loop invariant is true using a formal proof like that shown in the textbook and the course notes for {\sc Insertion-Sort} (prove the invariant holds initially, at every subsequent iteration, and at termination, according to the value of $j$,
the loop counter).\\

\vspace{5in}


\newpage

\item (8 points) Order the following functions in terms
of their order of growth (i.e., growth rate),
from lowest to highest:

\begin{center}
$n$lg$n$,\  $n +$lg$n$,\  $n!$,\  $n$,\  $n^2$,\  $2^n$,\  $n^{\frac{1}{2}}$,\  $4^n$\\
\end{center}

\vspace{.2in}

Provide a justification for your answers and 
indicate which of the functions, if any, grow at the 
same rate.



\end{enumerate}

\end{document}



