\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment 10\\ Solutions}
\end{center}
\ben
\item Suppose we are given the Minimal Spanning Tree $T$ of a graph
$G$. Now we take an edge $\{x,y\}$ of $G$ which is not in $T$ and
reduce its weight $w(x,y)$ to a new value $w$. Suppose the path from
$x$ to $y$ in the Minimal Spanning Tree contains an edge whose weight
is bigger than $w$. Prove that the old Minimal Spanning Tree is no
longer the Minimal Spanning Tree.
\So We can replace the edge whose weight is bigger than
$w$ with the edge $\{x,y\}$ resulting in a lower weight spanning tree.
\item Suppose we ran Kruskal's algorithm on a graph $G$ with $n$ vertices
and $m$ edges, no two costs equal. Suppose the the $n-1$ edges of
minimal cost form a tree $T$.
\ben
\item Argue that $T$ will be the minimal cost tree.
\So From Kruskal's Algorithm we will accept all the edges of $T$.
Then we have a spanning tree so no more edges are accepted.
\item How much time will Kruskal's Algorithm take.
{\em Assume} that the
edges are {\em given} to you an array in increasing order of weight.
Further,
{\em assume} the Algorithm stops when
it finds the MST. Note that the total number $m$ of edges is irrelevant as the
algorithm will only look at the first $n-1$ of them.
\So We do $n-1$ operations $UNION[x,y]$, each takes time $O(\ln n)$
so the total time is $O(n\ln n)$.
\item We define Dumb Kruskal. It is Kruskal without the SIZE
function. For $UNION[u,v]$ we follow $u,v$ down to their
roots $x,y$ as with regular Kruskal but now, if $x\neq y$,
we simply reset $\pi[y]=x$. We have the same
assumptions on $G$ as above. How long could Dumb Kruskal take.
Describe an example where it takes that long. (You can imagine that
when the edge $u,v$ is given an adversary puts them in the worst
possible order to slow down your algorithm.)
\So As $UNION[x,y]$ must take time $O(n)$ (as there are only
$n$ vertices) the whole algorithm will take time $O(n^2)$. This can
happen. Suppose the edges were, in order, $\{2,1\}$,$\{3,1\}$,$\{4,1\}$,
$\ldots$,
$\{n,1\}$. For the first edge we make $\pi[1]=2$. The second edge we
follow $1$ down to root $2$ and set $\pi[2]=3$. Now for the third edge
we follow $1$ to $2$ to root $3$ and set $\pi[3]=4$. On the $i$-th step
we are taking time $\sim i$ so it is a $\Theta(n^2)$ running time.
\een
\item Consider the graph on vertices $1,\ldots,7$ in which two vertices
are adjacent if they are either one or two apart. Define a weight
function on this graph by taking a pair of dice (or other random device)
and rolling them for
each edge to give the weight.
Apply Kruskal's algorithm to this
graph to find the MST showing all work.
\So xxx
\item Apply Prim's algorithm to the graph above to find the MST showing
all work.
\So
xxx
\een
\end{document}