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

\title{CS140 - Assignment 0\\\small{Due: Sunday,  9/1 at 11:59pm}}
\author{}
\date{}


\begin{document}
\maketitle

\begin{center}
\includegraphics[scale=0.6]{figures/xkcd_log.png}

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


\begin{itemize}
\item For this assignment you must work with a partner.   You can work with someone from either section.  If you would like help finding a partner, let me know \textbf{ASAP}.

\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 An important part of being a computer scientist is the ability
  to express solutions clearly and thoroughly.  Therefore, 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{[14 points]} Which is bigger?

For each of the two options below, state which one is larger (or if they're equal) and give a justification for your answer.  If the base of the log is not specified, then the answer should apply to all bases ($\ge 2$).  Your justification should be similar to those we looked at in class.  Do \textbf{not} simply plug these answer into a calculator (though you're welcome to check your logic that way).  For all variables (e.g., $x$ or $n$, assume they are positive).

\begin{enumerate}

\item $\log 10$ vs. $\log 20$

$\log 20$.  $20 > 10$ and log is a monotonically increasing number so $\log a > \log b$ if $a > b$.

\item $\log_4 n$ vs $\log_5 n$

$\log_4 n$.  They can do this with logic ( 	

\item $\log_5 75$ vs $\log_2 12$

\item $\log_7 24.5 $ vs $\log_5 12.5$

\item $\log x^4$ vs $\log x + \log x^3$

\item $((x^2)^2)^2$ vs $x^7$

\item $a^b$ vs. $b^a$ for constants $a$ and $b$, where $a > b > 3$.  For this one a \emph{proof} is challenging, so just give a reasonable justification for your choice.

\end{enumerate}


\item \textbf{[5 points]} Pseudocode

\begin{enumerate}

\item Write pseudocode for a function \texttt{dedup} that takes as input an array/list and returns a new array/list with all of the duplicates removed.  You don't have to necessarily follow the conventions used in class, but use something reasonable and be consistent.


\item What is the big-O running time of your function?  Give a brief (one sentence) justification.

\end{enumerate}


\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$\\
 \textbf{Note:} This cannot be solved exactly, so you'll need to explore other approaches for calculating, e.g., you can write a small program.
\item $2^n$
\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}


\end{enumerate}

\vspace*{.4cm}

\end{document}

