\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}