Lots Of Topics

Copyright © 2015 Bart Massey

1. One of the key elements of Kruskal's Algorithm is a Union-Find implementation. Union-Find is used for keeping track of which vertices of a forest are in the same connected component.

   Think of Union-Find as an ADT:

   UNION-FIND Carrier Set: Arbitrary set E
   Operations: init: E -> U; find: U -> E; union: U x U -> U
   Laws:
   find (init e; ) = e
   find (union u v) = find u or find v

   The basic idea here is that find gives some canonical element of a set U of elements, and union joins two sets to make a new set.

   The standard implementation is to give each element a parent pointer "wrapper" in init. The parent pointer always points toward the canonical representative, which is the element in the "upside down tree" with no parent pointer. Implement union by setting one tree's canonical representative to point at the other tree's representative. (Optimizations: after you walk up the tree in find, walk up again and adjust all the nodes you walk over to point directly at the canonical representative. Use find to find the canonical representative of both trees for union.)

   (a) Give pseudocode for init, find and union for an implementation of Union-Find. What is the complexity of your operations?

   (b) Implement your pseudocode. Test its correctness and performance using a methodology of your choice.

2. OK, you have a Union-Find implementation from (1). Go ahead and implement Kruskal's Algorithm. Test it, then try it on the graph whose weighted edge list is at http://svcs.cs.pdx.edu/cs350-summer2015/city-pairs.txt and output the total distance of the minimal spanning tree.

   (If you like, you may pay |E| lg |E| time to sort the edge list by weight rather than using a min-heap implementation. This would only hurt from an efficiency point of view if you were prepared to stop extracting edges early when the forest has been reduced to a single tree.)

3. There are three materials involved in the manufacture of Wertzial Widgets (WWs): we will call these materials X, Y and Z. Each WW requires a specified amount of X, Y and Z to manufacture. The X, Y and Z come from one of several conglomerations:

          Alphium (A): X
          Betium (B):  Y
          Cetium (C):  Z
          Deltium (D): XXXYYYZ (3X3YZ)
          Etium (E):   YYZZZZZ (2Y5Z)
          Ferium (F):  XXXXXXZZ (6X2Z)
          Gatium (G):  XXYYYYYYZ (2X6YZ)
          Herium (H):  YZZ (Y2Z)
   

   Give worst-case asymptotic polynomial time algorithms for the following problems, and indicate their big-O complexity.

   (a) Given: the amount of each material required to manufacture a WW. Solution: a collection of conglomerations of minimum cardinality (number of conglomerations in the collection) that contains sufficient materials to manufacture that WW. You may not waste material. That is, the total amount of materials in the conglomerations should exactly equal the WW materials cost.

   (b) Optional Extra Credit: As in (a), but with waste of material allowed.

   Hints: Memoization or dynamic programming will be needed here. An implementation is not required, but might be very useful in testing your solution. If you try part (b), the trick is to watch out for cases where adding a conglomeration does not reduce the total amount of material. Otherwise, you may end up with infinite recursion.