I’ve decided to spend some time and work on getting a better understanding of algorithms and system design. I find the topic super interesting and think there are tremendous benefits to learning and applying these algorithms. So, I begin my foray into algorithms with courseras algorithms course from Princeton which so far has been amazing.
I’m planning on doing a write up on most of the algorithms I’m learning, this helps me understand and keep the material fresh in my head, so stay tuned.
Union-Find (disjoint set)
Basically, I’m going to discuss three different variations of the union find algorithm.
- Weighted Quick-Union (with path compression)
I’ll try and point out the pros, cons and complexities of each. All these variations will share two common methods, a
connected(p,q) and a
union(p,q) method, both of which take the array index of the nodes we’re comparing or uniting. Enough rambling, lets have a look.
We’ll start with probably the simplest of the three, the quick-find. Here is the class initializer which will initialize the object with
This should give us an object containing our array. Visually, this would look something like this:
As it stands, we can think of each node as its own set, at this point nothing is connected. Lets add the
union method and do some union-ing?.
So, actually this is the complete class as I’ve got
union calling the
connected method to see if nodes are connected before continuing. So we’re going to union a few nodes then come back and look at the method.
First, we call
qf.union(3,2), we want to set the value at array index 3 to 2. First, is the call to
connected checking if the values at index p equals value at index q. If they are connected, we return from the method.
Moving on, we find the p and q’s values based on the passed in array index. Next, we iterate over the array and check each value against the
p_val if they are equal we know we have to change the value at that particular array index to the
I’m sure your starting to notice the problem with this implementation, finds are quick O(1) array access which is great, however every
union command needs to iterate over the whole array replacing every node with a value of
p with the value at
q making this O(n). This algorithm has the potential to be a
run in O(n^2) time, assuming the
union function costs
n accesses and we have
Okay, that’s about all i’ve got for now. I’ll post a link to part II (quick-union and weighted quick-union) once I have it up.