Solutions to Assignment 5


March 26

soltns5.pdf
or as three separate files:soltns5a.pdf    soltns5b.pdf   soltns5c.pdf

If you have trouble viewing in the browser, download to your desktop and try viewing from there.

March 28
Transitive closure.

For each vertex v in the graph:
     Do a DFS (or BFS) from v and let S be the set of all vertices marked
     For each w in S which is different from v, add the edge vw to the transitive closure

Transitive reduction.

This problem is a bit tricky if the graph has cycles. Let us assume that it does not.
First compute the transitive closure. Then:

For every vertex u
    For every vertex v not equal to u
        For every vertex w not equal to u or v
            If uv, vw and uw are edges, delete uw


Note: this may not always give the one with the minimum number of edges if the graph has a cycle.
Consider the case of a graph with three vertices and all 6 directed edges.
One transitive reduction has edges: 12, 23, 31
Another one has edges: 12,21,13,31


April 2
Union by weight

The reason is essentially the same as that given in the last two paragraphs of Section 16.1 of the notes.

A find operation takes at most the maximum depth of any of the trees. Initially all trees have zero depth.

The only way a tree can increase its depth is when two trees are merged together.

The leader of the smaller tree has its weight at least double for each merge, since it gains all of the nodes
of the larger tree as children.

Since no tree has more than n nodes, a node can double its weight at most log_2 (n) times so the maximum depth of
any tree is at most log_2 (n).