
\documentclass{article}
\usepackage{epsfig,amssymb}
\usepackage{hyperref}
\usepackage{fullpage}
\pagestyle{empty} %
\setlength{\parindent}{0pt} %
\setlength{\parskip}{.25cm}
\newcommand{\comment}[1]{}

\begin{document}

\begin{center}
{\Large\bf CSE 235 \hfill  Homework 04\hfill Fall 2007}\\
{\small Due 1:30PM, Friday, November 9th, 2007}
\end{center}
\hrule

\vspace{.50cm} Name/CSE Login \rule{2in}{.001in}

\vspace{.50cm} Name/CSE Login \rule{2in}{.001in} \\

\textbf{Instructions} Follow instructions \emph{carefully}, failure
to do so may result in points being deducted.  Clearly label each
problem and submit the answers \emph{in order}. It is highly
recommended that you typeset your homework using \LaTeX\ or a
similar typesetting system. Staple this cover page to the front of
a hardcopy of your assignment for easier grading.
%Be sure to submit any programming files via the webhandin
%(\url{http://www.cse.unl.edu/~cse235/handin}).
Late submissions \emph{will not be accepted}.  Be sure to show sufficient work to
justify your answer(s).  If you are asked to prove something, you
must give as formal, rigorous, and complete proof as possible. You
are to work individually, and all work should be your own. The CSE
academic dishonesty policy is in effect (see
\url{http://www.cse.unl.edu/undergrads/academic_integrity.php}).

\textbf{Material} (Partial Orders), Algorithms, Algorithm Analysis, Number Theory

\textbf{Partner Policy} You may work in pairs, but you must follow
these guidelines:
\begin{enumerate}
 \item You must work on \emph{all} problems
       \emph{together}.  You may not simply partition the work between
       you.
 \item You must use \LaTeX\ and you may divide the typing duties however
       you wish.
 \item You may not discuss problems with other groups or
       individuals.
 \item Hand in only one hard copy under the first author's name.
\end{enumerate}

~~~~~\begin{tabular}{|l|r||l|} \hline
Problem & Points & Score \\
\hline %
A & 10 & ~\\
\hline
B & 10 & ~\\
\hline
C & 8 & ~\\
\hline
D & 8 & ~\\
\hline
E & 8 & ~\\
\hline
F & 8 & ~\\
\hline
G & 8 & ~\\
\hline
H & 8 & ~\\
\hline
3.1.24 & 8 & ~\\
\hline
3.1.30 & 8 & ~\\
\hline
3.2.8 & 8 & ~\\
\hline
3.2.24ab & 8 & ~\\
\hline

%Program
%\multicolumn{2}{|l||}{Program} & ~\\
% \hline
%Correctness & 35 & ~\\
%\hline
%Style/Doc & 5 & ~\\
%\hline\hline
%Total & 100 & ~\\
%\hline
\end{tabular}\\

\textbf{Topics:} Algorithms, Algorithm Analysis, Asymptotics.

For 3.2.24ab, use the \emph{definitions}; do not use limits.

When asked to give an algorithm, be sure to give good
pseudocode.  In addition, also analyze your algorithm and give
an asymptotic characterization. You may find the
\texttt{algorithm2e} package useful in typesetting algorithms.

\textbf{Problem A} Let
 $$\begin{array}{rcl}
   f(n) & = & (k_1)^{c_1 n} \\
   g(n) & = & (k_2)^{c_2 n} \\
   \end{array}$$

Where $k_1, k_2, c_1, c_2$ are all real numbers greater than 1.  Under what conditions can
you say that $f(n) \in \mathcal{O}(g(n))$

\textbf{Problem B}
\begin{enumerate}

  \item[(a)] What is wrong with the following argument showing that
             $$1^k + 2^k + \cdots + n^k \in \mathcal{O}(n^{k+1})$$
	
	     \emph{proof} Let $f(n) = 1^k + 2^k + \cdots + n^k$ and $g(n) = n^{k+1}$.
	     Then we have that
	      $$\begin{array}{rcl}
	        \lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} & = & \lim_{n\rightarrow\infty} \frac{1^k + 2^k + \cdots + n^k}{n^{k+1}} \\
              & = & \lim_{n\rightarrow\infty} \frac{1}{n}\left[\frac{1^k + 2^k + \cdots + n^k}{n^{k}}\right] \\
              & = & \lim_{n\rightarrow\infty} \frac{1}{n}\left[\frac{1^k}{n^k} + \frac{2^k}{n^k} + \cdots + \frac{n^k}{n^k}\right] \\
              & = & \lim_{n\rightarrow\infty} \frac{1}{n}\left[\left(\frac{1}{n}\right)^k + \left(\frac{2}{n}\right)^k + \cdots + \left(\frac{n}{n}\right)^k\right] \\
              & = & \lim_{n\rightarrow\infty} \frac{1}{n}\left[0 + 0 + \cdots + 1\right] \\
              & = & \lim_{n\rightarrow\infty} 0\cdot\left[0 + 0 + \cdots + 1\right] \\
              & = & 0 \\
		\end{array}$$ %
    Therefore, $f(n) \in \mathcal{O}(g(n))$.

  \item[(b)] Prove that
             $$1^k + 2^k + \cdots + n^k \in \mathcal{O}(n^{k+1})$$

\end{enumerate}

\textbf{Problem C} Order the following functions in increasing
order of growth.  You need not give a formal proof for each.
 $$6n\log{(n)} + 2n, \left(\frac{1}{3}\right)^n, n^n, \log{\log{(n)}},$$
 $$\log^2{(n)}, \frac{1}{n}, 2^{10}, n-n^3+6n^5, \frac{n}{\log{(n)}}, n!,$$
 $$2^{\log{(n)}}, 2^n, 2^4n, 4^2n, 3n+\log{(n^{100})}, \log{(n)}\log{\log{(n)}}$$

\textbf{Problem D} Give an example of a positive function
$f(n)$ such that $f(n)$ is neither $\mathcal{O}(n)$ nor
$\Omega( n )$ (hint: make it a discontinuous function depending
on if $n$ is odd or even).

\textbf{Problem E} Give and analyze an algorithm for the
following problem.

  Given an $n$ vertex convex polygon described by coordinates
  $\{(x_1,y_1), \ldots, (x_n,y_n)\}$, find the three vertices whose
  corresponding triangle has maximum perimeter.

\textbf{Problem F} Three or more points are \emph{co-linear} if
they lie on the same line in $2$-space.  Give and analyze an
algorithm for the following problem.

  Given a list of $n$ points, find the maximal number of
  co-linear points.

\textbf{Problem G} What's wrong with the following about the
existence of a polynomial-time algorithm to find a factor an
integer $n$: For each integer $i = 2, \ldots \sqrt{n}$, simply
check if $n$ is divisible by $i$.  Output the first such
integer $i$ that does divide $n$, otherwise return that $n$ is
prime.  If division is considered our elementary operation,
then clearly the algorithm is $\mathcal{O}(\sqrt{n})$ and so we
have a polynomial time algorithm for factorization.

\textbf{Problem H} The space complexity of an algorithm is the
greatest amount of memory required at any one instant \emph{not
counting the input}.  What is the space complexity of Linear
Search (page 170), Insertion Sort (page 174), and Algorithm 6
(page 175)?

\end{document}
