\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}

\title{CS140 - Assignment 2\\\small{Due: Sunday,  Sept. 11 at 11:59pm}}
\author{}
\date{}


\begin{document}
\maketitle

\begin{center}
\includegraphics[scale=0.6]{figures/tsp.jpg}

\footnotesize{http://xkcd.com/399/}
\end{center}


\begin{itemize}
\item[] This problem set should be done in the pairs within your learning group.  If your group has five members, you may do a group of three.
\item[] You must use \LaTeX $\;$ to format your solution; one person should upload the pdf
  to gradescope.
\end{itemize}

\begin{enumerate}

\item \textbf{[10 points]} The Geometric Series
 \begin{enumerate}
 \item Use induction on $n$ to show that for all integers $n \geq 0$
 \[
   1 + a + a^{2} + a^{3} + \ldots + a^{n} = \frac{a^{n+1} - 1}{a - 1}
 \]
where $a$ is some arbitrary real number other than 1.
Please make sure to write
your proof carefully, with a base case, induction hypothesis, induction
step, and conclusion.

\item Explain where your induction proof relied on the fact that $a \neq 1$. 
\item What does the sum evaluate to when $a = 1$?
 \end{enumerate}

\vspace*{.2cm}

\item \textbf{[12 points]} Solving Recurrences

Give asymptotic upper and lower bounds for $T(n)$ in each of the
following recurrences.  Assume that $T(n)$ is constant for $n \leq 2$.
Make your bounds as tight as possible (in other words, give $\Theta$ bounds
where possible) and make sure to justify your answers.
(Note: you may want to read appendix A.1 in the textbook, which has
some summation properties.)

\begin{enumerate}
\item $T(n) = 4T(n/2) + cn$
\item $T(n) = T(n-1) + n$
\item $T(n) = T(n-1) + 1/n$
\item $T(n) = T(9n/10) + n$
\end{enumerate}

\vspace*{.2cm}

\item \textbf{[20 points]} 3-part sort 

Consider the following sorting algorithm: First sort the first
two-thirds of the elements in the array. Next sort the last two thirds
of the array.  Finally, sort the first two thirds again.  Notice that
this algorithm does not allocate any extra memory; all the sorting is
done inside array $A$.  Here's the code: 

\begin{tabbing}
\hspace*{1cm} \= ThreeSort ($A$,$i$,$j$) \\
\> \hspace*{.5cm} \= {\bf if} \= $A[i] > A[j]$ \\
\>\>\> {\bf swap} $A[i]$ and $A[j]$ \\
\>\> {\bf if} $i+1 \geq j$ \\
\>\>\> {\bf return} \\
\>\> $k = \lfloor (j-i+1)/3 \rfloor$. \\ 
\>\> ThreeSort$(A,i,j-k)$ \ \ \ \ \ \= {\bf Comment:} Sort first two-thirds. \\
\>\> ThreeSort$(A,i+k,j)$ \> {\bf Comment:} Sort last two thirds.\\            
\>\> ThreeSort$(A,i,j-k)$ \> {\bf Comment:} Sort first two-thirds again! \\     
\end{tabbing}

\begin{enumerate}
\item  Give an informal but convincing explanation (not a rigorous proof 
by induction) of why the 
		approach of sorting the first two-thirds of the array, 
then sorting the last two-thirds of the array,
		and then sorting again the first two-thirds of the 
array yields a sorted array.  A few well-chosen 				sentences should suffice here. 

\item Find a recurrence relation for the worst-case running time of
ThreeSort.

\item Next, solve the recurrence relation using a recursion tree.

\item Double check that you got the right answer in the previous part
  by solving the recurrence using the master method.

\item How does the worst-case running time of ThreeSort compare with
the worst-case running times of Insertion Sort, Selection Sort, and 
Mergesort?
\end{enumerate}

\end{enumerate}
\end{document}
