due by the end of class Wednesday March 7 2001.
Recall that in a union-find data structure,
components are represented by directed trees,
find is performed by traversing from a node to the root of its tree,
union is performed by making the
root node of the first node's tree a child of the
root node of the second node's tree,
and weighted union is performed by making the
root node of the smaller of the two nodes' trees a
child of the root node of the larger of the two nodes' trees.
Show that in a union-find data structure which
is initialized to a forest of n trees with 1 vertex each,
performing m finds and n-1 unions
can take Theta(mn) time, whereas
performing m finds and n-1 weighted unions takes O(m lgn) time.
For a connected graph G,
let P(G) be the probability that the
randomized graph algorithm
returns a min cut of G.
For the two graphs shown below,
- give the lower bound on P(G)
from the formula proved in class
- give the best lower bound on P(G) you can
(you will get a bonus mark if you
determine P(G) exactly)
- using your answer from 2.1 or 2.2,
determine the number of times you
would have to run the algorithm
so that the probility that a min cut
is eventually found is at least 90%.
|\ /| |\ /| |\ /|
| X | | X | | X |
|/ \| |/ \| |/ \|
In this question you will prove
that the randomized min cut algorithm is correct.
Let G be a loopless multigraph with
at least three vertices, and let
G* be the loopless multigraph obtained by
contracting an edge e of G, and removing
and resulting loops.
(a) if C is a min cut of G which does not contain e,
then C is a min cut in G*, and that
(b) if C is the only min cut of G,
and C does contain e,
then the size of a min cut of G* is greater
than the size of a min cut of G.