\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}
\\ Due April 30, in Recitation}
\end{center}
\begin{quote}
Historically, the main equalizing force — both between and within countries — has been the diffusion of knowledge and skills. However, this virtuous
process cannot work properly without inclusive educational institutions and continuous investment in skills. This is a major challenge for all
countries in the century underway. -— Thomas Piketty
\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
\item Consider Kruskal's Algorithm for MST on a graph with vertex set
$\{1,\ldots,n\}$. Assume that the order of the weights of the edges
begins $\{1,2\}, \{2,3\}, \{3,4\},\ldots, \{n-1,n\}$. (Note: When
$SIZE[x]=SIZE[y]$ make the first value the parent of the second.
In particular, set $\pi[2]=1$, not the other way around.)
\ben
\item Show the pattern as the edges are processed. In particular,
let $n=100$ and stop the program when the edge $\{72,73\}$ has
been processed. Give the values of $SIZE[x]$ and $\pi[x]$ for all
vertices $x$.
\item Now let $n$ be large and stop the program after $\{n-1,n\}$ has
been processed. Assume the ordering of the weights of the edges
was {\em given} to you, so it took zero time. How long, as an
asymptotic function of $n$, would this program take. (Reasons, please!)
\een
\item Consider Prim's Algorithm for MST on the complete graph with vertex set
$\{1,\ldots,n\}$. Assume that edge $\{i,j\}$ has weight $(j-i)^2$. Let
the root vertex $r=1$. Show the pattern as Prim's Algorithm is applied.
In particular,
Let $n=100$ and consider the situation when the
tree created has $73$ elements and $\pi$ and $key$ have been updated.
\ben
\item What are these $73$ elements.
\item What are $\pi[84]$ and $key[84]$.
\een
\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}