\documentclass[12pt]{article}
\usepackage{url}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}


\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2012 \\
	\rm
	Homework 6  \\
	Due Tuesday, February 28
\end{center}

\begin{enumerate}
	 \item \Points{35} \Name{Headbook!}
	 Headbook, the wildly successful Shmorbodian social networking site, models its social networks as unweighted undirected graphs, where vertices are people and edges are friendships between people.   Headbook computes a number of measurements on its social networks and one important one is called the \emph{diameter}.    The \emph{diameter} of a graph is the maximum distance between all pairs of vertices.   Recall that the distance between a pair of vertices is the length of a \emph{shortest path} between them.  So the diameter is the maximum of all the pairwise distances between points, where each distance is the length of a shortest path between those points.  For this reason, distance is called a ``maxi-min'' measure because its the maximum of minimums (shortest paths).  A small diameter indicates that the network is a tight cluster of friends whereas a large diameter suggests  a more ``spread out''  collection of friends.
	 
Headbook represents its graphs using adjacency lists.

	\begin{enumerate}
		\item Describe an algorithm for computing the diameter of an undirected graph and derive its running time.  Your algorithm should be simple and run in time $O(n^k)$ for some constant $k$.  
	
		\item It turns out that some social networks have no cycles (they are \emph{acyclic}).  Describe an algorithm for computing the diameter of an undirected acyclic graph.      Your algorithm should run in time $O(n)$ and you should explain why your algorithm runs in this much time.  (Hint:  There are several different and equally good solutions to this problem.  One is a modification of the key idea in the topological sorting algorithm.  Another is to use depth-first or breadth-first search some small number of times.)
						
		\item In a few sentences, give a convincing explanation of the correctness of your algorithm.  (That is, we're asking for a ``sketch'' of how the proof would go.)
	\end{enumerate}
	
\end{enumerate}

\end{document}