%% To students who wish to submit their homework in LaTeX format:
%%   Put your name(s) in the appropriate place.
%% Don't forget to include a statement with each problem indicating
%%   the contribution of each partner!

\documentclass[11pt]{article}

\usepackage{fullpage}

\newcommand{\solution}{\bigskip\hrule\bigskip}
\newcommand{\problembreak}{\bigskip\hrule\bigskip}

\begin{document}

\begin{center}
\Large CS4104 Fall 2010 Homework Assignment 2\\
Due at 11:00pm on Wednesday, September 8\\
50 Points
\end{center}
\vspace*{0.10in}
\medskip

\textbf{Pledge:
I (we) have not received unauthorized aid on this assignment.
I (we) understand the answers that I (we) have
submitted.
The answers submitted have not been directly copied from another
source, but instead are written in my (our) own words.}

\bigskip
%PutYourNameHere, PutYourIDNumberHere
%Put second name/ID here if there is one

\paragraph{1.}
[15 points] Find a growth rate that cubes the run time when we double
the input size.

\solution
% PUT YOUR SOLUTION HERE

\problembreak

\paragraph{2.}
[20 points]
\begin{enumerate}
\item[(a)] Arrange $n^2$ apples in a square.
From each row find the largest one and let $A$ be the smallest of
these.
From each column find the smallest one and let $B$ be the largest of
these.
Which apple is bigger, $A$ or $B$?

\solution
% PUT YOUR SOLUTION HERE

\problembreak

\item[(b)] The lower bound on the worst cost of a problem has been
defined as
\[ \min_{{\cal A} \in {\cal A}_M} \left\{
\max_{I \in I_n} f_{\cal A}(I)\right\}.\]

Is this the same as
\[ \max_{I \in I_n} \left\{
\min_{{\cal A} \in {\cal A}_{M}} f_{\cal A}(I)\right\}?\]

\end{enumerate}

\solution
% PUT YOUR SOLUTION HERE

\problembreak

\paragraph{3.}
[15 points]
A chocolate company decides to promote its chocolate bars by including
a coupon with each bar.
A bar costs a dollar and with $c$ coupons you get a new bar.

How much chocolate is a dollar worth?

Be careful! This problem is not particularly hard, but its not as
trivial as it might seem if you are not paying attention.

\solution
% PUT YOUR SOLUTION HERE

\problembreak

\end{document}
