I've posted the first assignment on the course website.

http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f09/www/

## Monday, September 14, 2009

Subscribe to:
Post Comments (Atom)

skip to main |
skip to sidebar

Subscribe to:
Post Comments (Atom)

A good additional problem for this assignment is the following:

ReplyDeleteConstruct an example of the arbitrary (i.e unweighted) union algorithm with path compression with the following properties: It has n nodes. The number of finds, m, is n/2. The cost of each find is log(n/2).

Hint: Make use of binomial trees.

Any hints on 2.A? :-)

ReplyDeleteSorry, my bad --- it should be O(m + n log n). I'll fix the HW...

ReplyDelete