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


\begin{document}

\begin{center}
{ \Large \bf CMPU 241 - Algorithmics}\\
  {\bf Spring 2020 \\
 Assignment 1\\
 Due: Thursday, Feb. 6th, by midnight\\}
\vspace{.15in}
NAME: (2 points)\underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\\
\vspace{.15in}

\end{center}


\vspace{5mm}


\begin{enumerate}
\item (8 points) Consider sorting $n$ numbers stored in array $A$ by first finding the 
smallest element of $A$ and exchanging it with the number stored in $A[1]$. Then 
find the second smallest element of $A$, and exchange it with $A[2]$. Continue in this 
manner for the first $n-1$ elements of $A$. This algorithm, called {\sc Selection-Sort}, 
is 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}


\begin{enumerate}
\item[(a)] (1 point) Give the line number(s) of the basic operation in the algorithm\\

\vspace{.25in}

\item[(b)] (2 points) Write a nested summation to describe the number of times the basic operation of {\sc Selection-Sort} is executed on an input of size $n$ and then express this summation as a closed-form solution.

\vspace{.75in}



\item[(c)] (2 points) Why does the outer for loop of the algorithm need to run for only the first $n-1$ elements?\\


\vspace{.5in}

\item[(d)] (3 points) Are there best-case and worst-case asymptotic running times for {\sc Selection-Sort}? If so, give the best-case and worst-case running times of the algorithm in $\Theta$ notation. If not, give the worst-case running time in $\Theta$ notation. Explain your answer.\\


\end{enumerate}
\newpage

\item (4 points) Answer true or false. Use the definitions of $\mathcal{O}$, $\Theta$, and $\Omega$ to determine whether the following assertions are true or false. Briefly justify your answers.
\begin{enumerate}
\item[a.] $(n^2(n+1))/2 \in O(n^3)$\\

\vspace{10mm}

\item[b.] $n(n+1)/2 \in O(n)$\\

\vspace{10mm}

\item[c.] $n(n+1)/2 \in \Theta(n^3)$\\

\vspace{10mm}

\item[d.] $n(n+1)/2 \in \Omega(n)$\\

\end{enumerate}

\vspace{10mm}

\item (4 points) For each of the following functions, indicate the set $\Theta(g(n))$ the function belongs to. Show your work in simplifying these expressions to arrive at each answer.\\
\begin{enumerate}
\item[a.] $(n^2 + 1)^{10}$\\

\vspace{10mm}

\item[b.] $\sqrt{10n^2 + 7n +3)}$\\

\vspace{10mm}

\item[c.] $2^{n+1} +\ 3^{n-1}$\\

\vspace{10mm}


\item[d.] $\lfloor \lg n \rfloor$ \\

\end{enumerate}

\item (2 points) Answer Yes or No and provide a brief justification for each question below:\\
\begin{enumerate}
\item[a.] Is $2^{n+1} \in O(2^n)$?\\

\vspace{10mm}

\item[b.] Is $2^{2n} \in O(2^n)$?

\end{enumerate}

\end{enumerate}

\end{document}



