
\bigskip
\handout{Homework 2,  Due Wednesday, January 17, 11:59 pm}
\bigskip

\bigskip
Turnin instructions:  Electronic submission on gradescope using the CSE 421 gradescope site.   Submit the assignment as a PDF,  with separate pages for different numbered problems.  Problems consisting of multiple parts (e.g., 2a, 2b) can be submitted on the same page.

\problem{1 (10 points)}

Order the following functions in increasing order by their growth rate:
	\begin{enumerate}
		\item $n^3$
		\item $(\log n)^{\log n}$
		\item $2^{\sqrt{\log n}}$
		\item $2^{n/10}$
        \item $(\log n)^3$
	\end{enumerate}
	
Explain how you determined the ordering.


\problem{2 (10 points)}

We say that $T(n)$ is $O(f(n))$ if there exist $c$ and $n_0$ such that for all $n> n_0$, $T(n) < cf(n)$.   Use this definition for parts a and b.

\begin{itemize}
    \item[a)]
    Prove that $4n^2 + 3n\log n + 6n  +20\log^2 n + 11$ is $O(n^2).$  (You may use, without proof, the fact that $\log n < n$ for $n\ge 1$.)
    \item[b)]
    Suppose that $f(n)$ is $O(r(n))$ and $g(n)$ is $O(s(n))$.  Let $h(n) = f(n)g(n)$ and $t(n) = r(n)s(n)$.   Prove that $h(n)$ is $O(t(n))$.
 
\end{itemize}




\problem{3 (10 points)} Give an algorithm for efficiently computing the {\it number} of shortest paths in an undirected graph between a a pair of vertices.  Suppose that you have an undirected graph $G=(V,E)$ and a
pair of vertices $v$ and $w$.  Your algorithm should compute the number of shortest $v-w$ paths in $G$.  Since this graph is unweighted, the length of a path is defined to be the number of edges in the path.


Your algorithm should have run time $O(n+m)$ for a graph of $n$ vertices and $m$ edges.  If there is no path from $v$ to $w$,  your algorithm should report an error.

\medskip
You should explain why your algorithm is correct and justify the run time of the algorithm.

\problem{4 (10 points)} The {\it diameter} of an undirected graph is the maximum distance between any pair of vertices.  If a graph is not connected, its diameter is infinite. Let $G$ be an $n$ node undirected graph, where $n$ is even.  Suppose that every vertex has degree at least $n/2$.  Prove that $G$ has diameter at most 2.

\problem{5 (10 points) Edge Coloring} Given an undirected graph $G = (V, E)$ with $n$ vertices such that the degree of every vertex of $G$ 
is at most $k$. Prove that we can color the edges of $G$ with at most $2k-1$ colors such that any
pair of edges $e$ and $f$ which are incident to the same vertex have distinct colors.

\medskip
You should prove this result by giving an algorithm to color the edges of $G$ with at most $2k-1$ colors such that any pair of edges $e$ and $f$ which are incident to the same vertex have distinct colors.  You will also need to justify that your algorithm finds a valid edge coloring with at most $2k-1$ for graphs of degree at most $k$.  You should describe your algorithm using pseudo-code, which allows you to use a mix of English language statements and control structures. 