\documentclass[12pt]{article}
\usepackage{fullpage}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2003\\
\rm
Homework 7b\\
Due on 10/24/03 (Friday at 2pm)\\
\end{center}
\begin{enumerate}
%Ask why it would be difficult to modify the first part to work on directed graphs?!?

\item \textbf{[30 Points] Detecting Cycles!}
\begin{enumerate}
\item Consider an \textbf{undirected graph} with $V$ vertices and $E$ edges.
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 $O(V+E)$ time.  (That is,
whether at least one of its components has a cycle.)
You should assume that the graph is represented by an adjacency list.
Carefully explain your algorithmic modification, why it will correctly determine
when a cycle exists (if and only if it exists).
Also carefully 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 above algorithm work if you use breadth-first search instead of depth-first
search?  Explain briefly.



\item 
%The algorithm that you described in the first part of this problem can easily be
%modified to work for directed graphs as well.  
%However, 
Now show how the topological sorting algorithm can be used to determine whether a
\textbf{directed graph} contains a directed cycle.  
Again, 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 carefully analyze its runtime.



\end{enumerate}

%Next time: make it $O(V) time
%The EC is kind of silly, too, because DFS works just as well.

\item \textbf{[20 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.  
Make sure that you understand this definition well before proceeding!

\begin{enumerate}
\item Now, 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(E+V)$ time.
You should justify why your algorithm is correct and carefully analyze and explain its running time.



%IMPORTANT: This problem actually makes very little sense given DFS does it better.
\item \textbf{[10 Points Extra Credit]} Describe a Dynamic Programming algorithm that finds
the diameter of a connected undirected acyclic graph in $O(E+V)$ time. Justify in a few sentences why
your program works, and why it achieves the desired runtime.



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