Assignment 6 due by the end of class Wednesday March 7 2001.
  1. 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.

  2. 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,
    1. give the lower bound on P(G) from the formula proved in class
    2. give the best lower bound on P(G) you can (you will get a bonus mark if you determine P(G) exactly)
    3. 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%.
    4. o---o    o---o---o---o
      |\ /|    |\ /|   |\ /| 
      | X |    | X |   | X |
      |/ \|    |/ \|   |/ \| 
      o---o    o---o---o---o
      
  3. 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. Prove that (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.