notes01.pdf

CSE 2320 Notes 1: Algorithmic Concepts
(Last updated 1/20/16 10:10 AM)
1.A. A SIMPLE ALGORITHMIC PROBLEM - MAINTAINING DISJOINT SUBSETS
Sedgewick 1.2 and 1.3
Abstraction:
Set of n elements: 0 . . n - 1
Initially all elements are in n different subsets
find(i) - Returns integer (“leader”) indicating which subset includes i
i and j are in the same subset ⇔ find(i)==find(j)
union(i,j) - Takes the set union of the subsets with leaders i and j.
Implementation 1: ( http://ranger.uta.edu/~weems/NOTES2320/uf1.c )
Initialization:
for (i=0; i<n; i++)
id[i]=i;
find(i):
return id[i];
unionFunc(i,j):

0
0

1
1

2
2

3
3

4
4

2
2

3
3

4
4

for (k=0; k<n; k++)
if (id[k]==i)
id[k]=j;

Implementation 2: ( http://ranger.uta.edu/~weems/NOTES2320/uf2.c )
find(i):
while (id[i]!=i)
i=id[i];
return i;
unionFunc(i,j):
id[i]=j;

0
0

1
1