%%% Fall 2004, HMW 5
\documentclass[11pt]{article}
\usepackage{epsf}
\usepackage{pslatex}
\setlength {\topmargin}{0in}
\setlength {\headheight}{0in}
\setlength {\headsep}{0cm}
\setlength {\textheight}{9in}
\setlength {\oddsidemargin}{0in}
\setlength {\evensidemargin}{0in}
\setlength {\textwidth}{6.5in}
\setlength {\parskip}{0cm}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
\begin{document}
\thispagestyle{empty}
\begin{center}
{\bf \large ECE G205 Fundamentals of Computer Engineering} \\
{\bf Fall 2004} \\[0.5cm]
{\large \bf Homework 5: Due by Monday November 8 2004} \\
\end{center}
{\large
\vspace*{2cm}\noindent
\begin{itemize}
\item This test contains $4$ problems. They allow you to earn
$100$ points.
\item Show your work, as partial credit can be given. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it. \textbf{Be neat}.
\item {\bf No late submissions will be accepted.}
\item Only homework returned in a 9in $\times$ 12in envelope
will be accepted. (If you cannot find such envelope, ask the
Instructor.) Please, write your name and the class name (ECE
G205) on the envelope (write clearly, please).
\item For the problems that requires coding an e-mail to
BOTH TAs should be sent that contains the code and the
executable of a (single) program that implements the
solutions to the problem as functions.
\end{itemize}
\vspace*{3cm}
Write your name here:\
\hrulefill
}
\setcounter{page}{0}
%----------------------------------------------------------------------
\newpage
\begin{itemize}
\item {\bf Problem \# 1\ \ [30 points]}.
Describe (pseudo-code or C++) a Boolean algorithm that given
as input an undirected graph $G=(V,E)$ preprocesses its input in
$O(V+E)$ time and in $O(1)$ time returns whether the graph is
connected or not, i.e., whether there is a path between any two
nodes in $G$. (No program is needed for this problem.)
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 2\ \ [40 points]}. Implement BFS, DFS
and the Dijkstra algorithm in C++ using the C++ Standard
Template Library containers \texttt{vector} and
\texttt{deque}. (A program is needed for this problem.)
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 3\ \ [20 points]}. What is the
worst-case time complexity (in terms of $n$, the number of
the nodes in the graph) of Kruskal's algorithms when it is
executed on a graph $G$ that is \emph{complete} (i.e., in
which there is an edge between each pair of nodes)?
Justify your answer. (No program is needed for this problem.)
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 4\ \ [20 points]}. Are there graphs
for which Prim's algorithm for MST is slower than
Kruskal's algorithm? Justify your answer. (No program is
needed for this problem.)
\end{itemize}
\end{document}