\documentclass{article}
\pagestyle{empty}
\usepackage{graphicx}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Spring 2001}\\
\vspace{.3 in}
{\large Assignment 9}
\end{center}

\noindent
This assignment is due by the start of class on Tuesday, April 10.  You may collaborate
with your classmates to complete this assignment but you must reference your collaborators.  In addition,
you must do your own write-up.  This assignment is worth 100 points (65 points if handwritten).  


\vspace{.2 in}
\begin{enumerate}
\item
Give an algorithm for reducing the key of a record in a heap that runs in time $O(h)$,
where $h$ is the height of the heap.
\item
Problem 23.5-4 on page 494 of the text.
\item
Problem 23.5-5 on page 494 of the text.
\item
A Bottleneck Spanning Tree (BST) of a connected graph $G$ is a spanning tree whose maximum weight edge
is a small as possible.   In other words, the cost of a spanning tree for this problem is
the weight of its maximum weight edge.  The problem is to find a spanning tree with minimum cost.
(Assume $G$ has $n$ vertices and $m$ edges.) 
\begin{enumerate}
\item
Suppose $T$ is an MST $G$.  Show that $T$ is also a BST of $G$.
\item
Give a weighted, connected graph $G$ and a BST, $T$, of $G$ such that $T$ is not an MST of $G$.
\item
By part (a) we can clearly reduce BST to MST.  But by part (b) we might guess
that there is a more efficient algorithm for finding a BST of $G$.  
\begin{enumerate}
\item
Suppose I tell you that the cost of a BST of $G$ is $W$.  Give an $O(m)$ algorithm that then finds a BST
of $G$.
\item
Suppose I simply want to know if the weight of a BST of $G$ is less than or equal to $W$.  Give an
$O(m)$ algorithm that answers this question.
\item
Now design an $O(m)$ algorithm that finds a BST of $G$.  Hint:  Use divide and conquer.
\end{enumerate}
\end{enumerate}
\item
Run the Floyd-Warshall algorithm on the digraph whose adjacency matrix is given below.
Show $D^k$ for $k=0,\ldots,5$.  (There are no self-loops, hence the 0's on the diagonal.
An $\infty$ indicates a lack of edge.)
\begin{tabular}{ccccc}
0 & $\infty$  & $\infty$  & -1  & 20 \\
$\infty$ & 0 & 5 & 3 & $\infty$ \\
$\infty$  & -2 & 0 & 1 & $\infty$ \\
1 & 2 & 2 & 0 & $\infty$  \\
3 & 3 & 2 & $\infty$ & 0 \\
\end{tabular}
\item

Let $G=(V,E)$ be a directed graph with $n$ vertices and $m$ edges.  The transitive closure of $G$,
denoted $G^T$, is the
graph with vertex set $V$ and edge set
\begin{displaymath}
E^T = \{ <\! u,w \!> \; | \; \mbox{there is a path from $u$ to $w$ in $G$}\}.
\end{displaymath}

Let $d(u,w)$ denote the length
of the shortest path from vertex $u$ to vertex $w$ in $G$.
The diameter of $G$ is defined to be
\begin{displaymath}
max \{ d(u,w) | \mbox{ there is a path from u to v in $G$} \}.
\end{displaymath}

An example of a graph and its transitive closure is shown in the 
figure above.
The diameter of the graph $G$ in the figure is 3.
What is the diameter of $G^T$?

\begin{figure}
\centering
\includegraphics{trans_closure}
\end{figure}

\begin{enumerate}
\item

Give an algorithm that takes as input the adjacency matrix $M$ and diameter $d$ of a directed graph $G$ and
outputs the adjacency matrix of $G^T$.  To receive full credit
your algorithm should run in time $O(d \cdot n^{\lg 7})$.  You may assume that $n$ is a power of 2.  (Hint:  Reduce the problem to
a problem we've studied that has an algorithm with running time $O(n^{\lg 7})$).

\item
Now suppose that $G$ is acyclic.  In this case we can assume, without loss of generality, that
the adjacency matrix of $G$ is upper triangular.  Give an algorithm for finding the transitive
closure of $G$ in time $O(n^{\lg 7}))$. (Hint:  Divide and conquer)   


\end{enumerate}


\end{enumerate}
\end{document}

