Due: Wednesday, February 15th, 2012

Write a good exam problem. It should be insightful, interesting, and have a short description. It should come with a complete solution.

One thought on “HW4

  1. I spoke with Manuel at the end of class, and he supported/encouraged the sharing of our submitted hw 4’s for studying purposes. If someone knows of a better forum (google docs?) for this purpose, perhaps we can move it over there?

    I’ll go first: During the union step of union find, we emphasized that the canonical element of the larger set (in terms of # of elements, ‘union-by-weight’) remains canonical of the union’d set. Kozen points out that this keeps the trees in logarithmic height. Another possible way is to union-by-rank where the height of the tree is used instead of the # of elements. Show that this approach also leads to logarithmic height/depth trees.

    A: Pretty straight forward. Follows a solution to one of the homework problems. A tree’s height is increased only when unioned with a tree of the same height. Starting with N sets of 1 element each they form N/2 sets of height 1. These then make N/4 sets of height 2 -> N/8 sets of height 3 etc.

    Follow up: If both methods produce logarithmic height trees, then why do we prefer union-by-weight?

    A: The issue comes up with path compression. Compressing a path may reduce the height of a tree, but it is difficult to know when and by how much. Continuing to union based on not-up-to-date heights can result in much deeper trees. However, path compression does not change the weight of the tree and therefore remains optimal for unions with path compression working.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s