\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}
\\ {\bf NOT} not be Submitted. \\ Happy Thanksgiving!
\end{center}
\begin{quote}
Fearing error and fearing truth are one and the same. Those
who fear making mistakes are incapable of discovery. When we
worry about making mistakes, the error within us becomes an
unmovable rock. In our fear, we cling to what we have declared
to be ``true" one day, or what has always been presented as such.
When we are driven by a thirst for knowledge, and not by the
fear of seeing a false security fade away, then error, like
suffering and sadness, passes through us without ever gaining
substance, and the trace it leaves is that of renewed knowledge.
\\ Alexander Grothendieck, {\em Rec\'oltes et Semailes}
\end{quote}
\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.
\item Suppose we ran Kruskal's algorithm on a graph $G$ with $n$ vertices
and $m$ edges, no two costs equal. {\em Assume} that the $n-1$ edges of
minimal cost form a tree $T$.
\ben
\item Argue that $T$ will be the minimal cost tree.
\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.
\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.)
\een
\pagebreak
\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.
\item Apply Prim's algorithm to the graph above to find the MST showing
all work.
\een
\begin{quote}
Among his co-workers in an Indian named Ganapathy. Ganapathy
often arrives late to work; on some days he does not come at all.
When he does come, he does not appear to be working very hard;
he sits in his cubicle with his feet on the desk, apparently
dreaming. For his absences he has only the most cursory of
excused (``I was not well") Nevertheless he is not chided.
Ganapathy, it emerges, is a particularly valuable aquisition
for International Computers. He has studied in America, holds
an American degree in computer science.
\\ J.M. Coetzee, {\em Youth}
\end{quote}
\end{document}