Understood Quick-Find algorithm is too slow if we have many union operations. We have to design a new algorithm to do better, let’s use a lazy approach where we try to avoid doing work until we have to: we could think the array as a set of trees where each entry contains a reference to its parent in the tree. Each element of the array has associated with it a root and we can say that two elements are connected if they have the same root.
Continue reading

Let’s assume our object can be identified by an integer number, we can use an integer Array as data structure for our solution (id[]) . In Quick-Find we consider two sites p and q are in the same component if id[p] is equal do id[q]. The initQuickFindUF function allocates the zeroed array and assign the slice that refers to that array to Elements; then go through it and set the value corresponding to each index ( *Elements[i] = i *).
Continue reading

Let's Start

Let’s start this new adventure in blogger-land with a series of post about Algorithms and Go. I choose this two characters because of two targets, to learn a new language ( Go ) and renew my neurons about the classic algorithms studied in the past; I want to mix an old ingredient with a new one. I’m sure this road could take me to perceive new approaches to common problems, and i’m sure this trip is going to be funny.
Continue reading

Author's picture

Giovanni Laquidara

Machine Teacher

Software Engineer

Rome, Italy