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

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

\noindent
This assignment is due by the start of class on Monday 10/29/01.  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
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 can then find 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 1:  Use divide and conquer.  Hint 2:  You can check if a graph is connected in time $O(n+m)$
using Depth First Search.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{document}

