\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2004\\
\rm
Homework 7a\\
Due on Friday, 10/15/04 (midnight)\\
\end{center}
\begin{enumerate}
\item \textbf{[30 Points] Detecting Cycles!}

\begin{enumerate}

\item Consider an \emph{undirected graph} with $V$
vertices and $E$ edges.  \emph{The graph may be disconnected.}
That is, the graph may consist of a number of separate
disconnected components.  Describe how depth-first search
can be used to determine whether or not a graph has a
cycle in linear---i.e. $O(V+E)$---time.  You should assume
that the graph is represented by an adjacency list.  Prove
your algorithmic modification is correct---why it will
detect some cycle in the graph (if and only if it exists).
Note: if a graph is disconnected, the algorithm should
return true when at least one of its components has a
cycle.  Finally, analyze its runtime, demonstrating that
it has the desired asymptotic behavior. (This problem
might require a bit of cleverness in the algorithm's data
structures in order to get the $O(V+E)$ time!)



\item Does your your algorithm necessarily work on 
\emph{directed} graphs? 
Explain Briefly



\item Does your above algorithm work if you use
breadth-first search instead of depth-first search?  
Explain briefly.



\item 
Show how the topological sorting algorithm can be used to
determine whether a \emph{directed} graph contains a cycle
(the graph may be disconnected).  The algorithm should
work in $O(V+E)$ time assuming the graph is represented as
an adjacency list.  Again, explain your algorithmic
modification, justify its correctness, and analyze its
runtime. Also, explain why your algorithm how your algorithm
deals with a graph that is disconnected.



\end{enumerate}

\item \textbf{[30 Points] Diameters.}  

In this problem we will consider connected undirected
graphs with no cycles.  The graphs are simply represented
with adjacency lists.  The distance between two vertices
in such a graph is just the \emph{minimum} number of edges
on a path between the vertices.  The \emph{diameter} of
the graph is the \emph{maximum} distance between all pairs
of vertices. \emph{Make sure that you understand this
definition well before proceeding!}

Describe an algorithm that utilizes one of the
reachability algorithms discussed in class to compute the
diameter of a connected undirected acyclic graph in $O(V)$
time.  You should justify why your algorithm is correct
and carefully analyze and explain its running time.



\end{enumerate}
\end{document}
