\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Spring 2004\\
\rm
Homework xx\\
Due on in class exercise\\
\end{center}
\begin{enumerate}
\item \textbf{[20 Points] Some Prim and Kruskal Games!}
In these exercises you'll explore what happens when you know that all
weights are integers in the range $[0,W]$.

\begin{enumerate}
\item {\bf Kruskal and Prim Games!} 
Suppose that all the edges in a graph are \emph{integers} in the range from
1 to $|V|$. How fast can you make Kruskal's algorithm run? What about Prim's?
How about if the edge weights are integers in the range from 1 to $W$ for some
\emph{constant} $W$?
Use the table below to guide you in filling out your results.
Note that:
\begin{itemize}
\item The top row in this table makes no restrictions: run-times there are the ones derived in class.
\item A sparse graph means that $E \in O(V)$.
\item A connected graph means that $E \in O(V^2)$.
\end{itemize}

\begin{center}
\begin{tabular}{|c|c|c|c|c|}\hline
& \multicolumn{2}{|c|}{Prim} & \multicolumn{2}{|c|}{Kruskal}\\\hline
& Sparse & Connected & Sparse & Connected \\
& Graph & Graph & Graph & Graph \\\hline\hline
$w \in {\cal R}$ & & & & \\\hline
$w \in \{1,2,\cdots,W\}$ & & & & \\\hline
$w \in \{1,2,\cdots,V\}$ & & & & \\\hline
\end{tabular}
\end{center}



%\item {\bf Prim Games!} CLRS, Exercise 23.2-5 (page 574).  Explain your answers carefully.
%(This problem might require a bit of cleverness in the algorithm's data structures!)



\end{enumerate}
\end{enumerate}
\end{document}
