Monday, September 14, 2009

Homework 1 posted

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


  1. 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).

    Hint: Make use of binomial trees.

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