A good additional problem for this assignment is the following:
Construct 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).
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