Fundamental Algorithms, Spring 1998

Assignment 10. Sets and graphs.

Given April 13, due Monday, April 20.

1.

The binomial tree (related to binomial heap, CLR, chapter 20) of height h+1, , is defined inductively. is a single element. We have been saying that a tree with a single element has height 1, although one could make a case for saying height 0. is made from two copies of , call them with root , and with root . In , none of the pointers is changes except that the parent pointer of is set to point to , and a child pointer of points to , if there are child pointers.

a.

Show that has height h+1 and nodes.

b.

The binomial coefficients, , satisfy the relation . From this, find a formula for the number of nodes at depth k in ,

c.

Show that has the fewest elements among all trees of height h that can be made using make_set and union operations, assuming that we are using the union by rank heuristic. Hint: Let be the sparsest tree of height h that can be made. Show that is made by joining two copies of , because any other join would either not increase the height, or have more elements than necessary.

2.

Suppose we have a family of disjoint sets represented by trees with parent pointers only. Show that the additional work to perform another m find operations is O(n+m), where n is the number elements, no matter which elements are being found. (The analysis with find and union is harder.)

3.

In an undirected graph, an edge, e, connects e.head to e.tail. A graph, , is a subgraph of G if every vertex of us a vertex of G, and every edge of is an edge of G. A tree is a connected subgraph with no cycles. A spanning tree is a subgraph containing all the vertices of G that is a tree. A spanning forest is a collection of subgraphs, one spanning tree for each connected component. The following algorithm finds connected components:

for ( x in V ) { makeset(x); }
for ( e in E ) {
   if ( ( x = find(e.head)) != ( y = find(e.tail)) )  union(x,y); }

a.

Add a line or two to make a list of edges that forms a spanning tree if G is connected and a spanning forest otherwise.

b.

Write code to make this spanning tree into a tree sense we used before. That is, there should be a root, parent pointers, and child lists.

• About this document ...