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

\title{CS140 - Assignment 1\\\small{Due: Sunday,  Jan. 29 at  8pm}}
\author{}
\date{}


\begin{document}
\maketitle

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

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


\begin{itemize}
\item This assignment should be done in either pairs or triplets with people from your learning community.

\item The purpose of this assignment is to encourage you to get to
  know your learning community better and to review proof-writing (from cs54)
  and asymptotics (from cs62).
  
\item This assignment must be typeset using \LaTeX.  You are
  encouraged to take the source file for the assignment and modify it by adding your solutions.  
\item Like the first assignment, you are
  expected to explain each step of your solution and to present your
  solutions clearly and precisely.  Part of the score on each problem
  will be for quality of presentation.  Note that correct answers
  without justification are not worth very many points!
\end{itemize}

\vspace*{.1cm}

\begin{enumerate}

\item \textbf{[4 points]} Sorting in practice  Pick two different sorting functions from a programming language
(e.g. \texttt{java.util.Arrays.sort}) and state what sorting algorithm is used.  They could be two different ways of sorting in the same language or two different languages. Make sure to cite your source.  Why do you think these choices were made?

\vspace*{.4cm}  

\item\textbf{[9 points]} Properties of Logs

To get you warmed up, here is an example proof showing that $\log_{b} xy = \log_{b} x + \log_{b} y$.

Let:

$k = \log_{b} xy$\\
$\ell = \log_{b} x$\\
$m = \log_{b} y$

We want to show that $k=\ell+m$.\\

- By the definition of logarithms, we know:

$b^{k} = xy$\\
$b^{\ell} = x$\\
$b^{m} = y$\\

- From these, by properties of exponents

$b^{k} = b^{\ell} b^{m} = b^{\ell + m}$\\

Taking the log of both sides, we obtain $k = \ell + m$, which is what we wanted to show.\\

Now give proofs for each of the following properties of logarithms.
Write your proofs out carefully.  You should assume that $a, b, c, n$
are positive \emph{real numbers} (not necessarily integers).

\begin{enumerate}
\item $\log_{b} a^{n} = n \log_{b} a$
\item $\log_{b} a = \frac{\log_{c} a}{\log_{c} b}$
\item $a^{\log_{b} n} = n^{\log_{b} a}$
\end{enumerate}

\vspace*{.4cm}

\item \textbf{[5 points]} Running Times 

Suppose you have algorithms that execute the following number of
operations as a function of the input size $n$.  If you have a
computer that can perform $10^{10}$ operations per second, for each
algorithm what is the largest (integer!) input size $n$ for which you
would be able to get the result within a minute?  Be as precise as
possible.  But, for once, no explanation necessary!
\begin{enumerate}
\item $60n^2$
\item $n^3$
\item $\sqrt{n}$
\item $n\log_2 n$
\item $2^n$
\end{enumerate}

\vspace*{.5cm}

\item \textbf{[52 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 problem 1 (\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''. 
\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}

\vspace*{.5cm}

\item \textbf{[20 points]} Writing proofs

  The objective of these two problems are to reinforce clear and precise
writing on mathematical material.

\begin{enumerate}
\item
There are two buses, A and B, about to take students on a field trip.
Bus A contains 50 1st grade students.  Bus B contains 50 2nd grade
students.  Before the buses leave, 8 students run out of Bus A and
onto Bus B.  The teachers then randomly choose 8 of the now 58
students on Bus B and force them to move to Bus A.  The buses then
(finally!) drive off.

Are there more 2nd grade students in Bus A or more 1st grade students
in Bus B?
\item Prove by induction that $\sum_{i=1}^n \frac{1}{i(i+1)} =
  \frac{n}{n+1}$ for all integers $n \geq 1$.  Do you need strong
  induction?  Why or why not?
\end{enumerate}

\vspace*{.4cm}


\end{enumerate}
\end{document}

