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

\title{CS140 - Assignment 1\\\small{Due: Sunday,  Jan. 28 at  10pm}}
\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 with a \emph{different} partner than you worked with last week.  If you would like help finding a partner, reach out ASAP.
\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{[40 points]} Asymptotics

Indicate whether each of the following statements
is true or false and then carefully {\bf prove} your answer using the formal
definition of Big-O notation and properties of logarithms from the last assignment \emph(hint, hint).  
Remember that to show that one of these statements is false, you must
obtain a formal contradiction; it does not suffice to just say ``false''. 

One useful summation:

\mbox{~~~} $\Sigma_{i=1}^n \frac{1}{i} = \ln n + c$


\begin{enumerate}
        \item $2^{n+1} \mbox{ is } O(2^{n})$.
        \item $2^{2n} \mbox{ is } O(2^{n})$.
        \item $3 n^{2} \log_{2} n + 16 n \mbox{ is } O(n^{3})$.
        \item $25 \log_{2} 8n^{10} \mbox{ is }  O(\log_{10} n)$.
        \item $8^{\log_{2} n} \mbox{ is } O(n^{3})$.
\end{enumerate}


\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{[3 points]} An improvement?

You decide to come up with a new sorting algorithm called \emph{$<$your\_name\_here$>$}sort.  You notice that $InsertionSort$ seems inefficient in how it finds the correct location to insert the next value.  You decide that rather than linearly searching one at a time to find the correct place, you use binary search to find the correct place.  Is this an improvement?  If yes, state the running time of this new algorithm.  If no, explain why this is not an improvement.  Be specific and clear.

\item \textbf{[5 points]} Intersection

Describe an algorithm and \emph{state the worse case running time} (in terms of $\Theta$ or $O$ where appropriate) to solve the following problem: given two lists of numbers $A$ and $B$ of lengths $m$ and $n$ respectively, return the intersection of the lists, i.e. all those numbers in $A$ that also occur in $B$.  You can use procedures that we've discussed in class, but no others (e.g. no hashtables).  You can assume that in any given list, the numbers are unique.  You will be graded on the efficiency of your solutions.

\end{enumerate}
\end{document}
