%% 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 8\\
Due at 11:00pm on Wednesday, October 20\\
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]
Show that \(\lfloor 3n/2 \rfloor + 1 = \lceil (3n + 1) /2 \rceil\).


\paragraph{2.}
[15 points]
Use constructive induction to find $f$'s growth rate if
\[f(n) = f(n/a) + f(n-n/a) + O(n).\]


\paragraph{3.}
[20 points]
Given an $n \times m$ array of numbers where each of the $n$ rows of
$m$ numbers are sorted in increasing order from left to right.
\begin{enumerate}
\item[(a)] Show that if we sort the numbers in each column in
  increasing order from top to bottom then the rows are still sorted
  in increasing order from left to right.

\item[(b)] Will the rows still be in increasing order from left to
  right if we sort the columns in decreasing order from top to bottom?
\end{enumerate}

\end{document}
