1-2 pages, Essay on union find, I need it done in 5 hours

Assignment 1: Disjoint Set Union

DS & A Disjoint Set Union Algorithms Slide # 2

Assignment 1: Disjoint Set Union ❏ Consider the following three Java classes given on the textbook’s website under the topic:

[1.5 CASE STUDY: UNION-FIND] https://algs4.cs.princeton.edu/15uf/ ➺ Quick Find (slow union) QuickFindUF.java ➺ Quick Union (possibly slow find) QuickUnionUF.java ➺ Quick Union (not slow find) WeightedQuickUnionUF.java

❏ For your convenience, the above three Java classes are available along with the specification of Assignment 1 on the Canvas webpage in a zipped file UnionFind-SourceCode.zip

❏ For each of the three given java classes do the following: ➺ Understand the given code and internal documentation { // comments } ➺ To each of the three given classes, add a public method displaySubsets( ) that takes no arguments

and prints out the contents of the id[ ] array from id[0] to id[n-1] in a clearly labelled output presentation. [Same code, just neatly print a one dimensional array]

➺ Replace each main ( ) method with the corresponding code given on the following 3 slides ➺ Run the three tests (a), (b) and (c) that are specified by each modified main ( ) ➺ Using a graphics editor, such as the graphics features of MS-Word or MS-Power-Point, draw the tree

diagrams that correspond to the results of displaySubsets( ). That should be three results from each of the three algorithms, a total of nine groups of subset diagrams: § For QuickFindUF: 1(a), 1(b) and 1(c) § For QuickUnionUF: 2(a), 2(b) and 2(c) § For WeightedQuickUnionUF: 3(a), 3(b) and 3(c)

➺ In a report of approximately 1-2 typed pages, compare the results of the three algorithms on each of the three tests (a), (b) and (c). In particular, focus on time efficiency and asymptotic bounds.

/**

* replacement main( ) for QuickFindUF.java

* Given a set of n = 64 objects

* Test QuickFindUF in three different ways and print the results

* Test 1(a): u(0, 1), u(1, 2), u(2, 3) ... u(62, 63)

* Test 1(b): u(0, 63), u(1, 63), u(2, 63) ... u(62, 63)

* Test 1(c): Merge into 16 subsets each of size 4, then 4 subsets each of size 16,

* then one subset of all 64 elements

*/

public static void main(String[] args) {

int n = 64;

QuickFindUF uf = new QuickFindUF(n);

for ( int k = 0; k < n-1; k++ ) uf.union(k, k+1);

uf.displaySubsets( ); // Test 1(a)

uf = new QuickFindUF(n); // equivalent to reset, old gets garbage collected

for ( int k = 0; k < n-1; k++ ) uf.union(k, n-1);

uf.displaySubsets( ); // Test 1(b)

uf = new QuickFindUF(n); // equivalent to reset, old gets garbage collected

for ( int k = 0; k < n-1; k += 4 )

{ uf.union(k, k+1); uf.union(k+2, k+3); uf.union(k, k+3); }

for ( int k = 0; k < n-1; k += 16 )

{ uf.union(k, k+4); uf.union(k, k+8); uf.union(k, k+12); }

uf.union(0, 16); uf.union(0, 32); uf.union(0, 48);

uf.displaySubsets( ); // Test 1(c)

}

/**

* replacement main( ) for QuickUnionUF.java

* Given a set of n = 64 objects

* Test QuickUnionUF in three different ways and print the results

* Test 2(a): u(0, 1), u(1, 2), u(2, 3) ... u(62, 63)

* Test 2(b): u(0, 63), u(1, 63), u(2, 63) ... u(62, 63)

* Test 3(c): Merge into 16 subsets each of size 4, then 4 subsets each of size 16,

* then one subset of all 64 elements

*/

public static void main(String[] args) {

int n = 64;

QuickUnionUF uf = new QuickUnionUF(n);

for ( int k = 0; k < n-1; k++ ) uf.union(k, k+1);

uf.displaySubsets( ); // Test 2(a)

uf = new QuickUnionUF(n); // equivalent to reset...

for ( int k = 0; k < n-1; k++ ) uf.union(k, n-1);

uf.displaySubsets( ); // Test 2(b)

uf = new QuickUnionUF(n); // equivalent to reset...

for ( int k = 0; k < n-1; k += 4 )

{ uf.union(k, k+1); uf.union(k+2, k+3); uf.union(k, k+3); }

for ( int k = 0; k < n-1; k += 16 )

{ uf.union(k, k+4); uf.union(k, k+8); uf.union(k, k+12); }

uf.union(0, 16); uf.union(0, 32); uf.union(0, 48);

uf.displaySubsets( ); // Test 2(c)

}

/**

* replacement main( ) for WeightedQuickUnionUF.java

* Given a set of n = 64 objects

* Test WeightedQuickUnionUF in three different ways and print the results

* Test 3(a): u(0, 1), u(1, 2), u(2, 3) ... u(62, 63)

* Test 3(b): u(0, 63), u(1, 63), u(2, 63) ... u(62, 63)

* Test 3(c): Merge into 16 subsets each of size 4, then 4 subsets each of size 16,

* then one subset of all 64 elements

*/

public static void main(String[] args) {

int n = 64;

WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);

for ( int k = 0; k < n-1; k++ ) uf.union(k, k+1);

uf.displaySubsets( ); // Test 3(a)

uf = new WeightedQuickUnionUF(n); // equivalent to reset...

for ( int k = 0; k < n-1; k++ ) uf.union(k, n-1);

uf.displaySubsets( ); // Test 3(b)

uf = new WeightedQuickUnionUF(n); // equivalent to reset...

for ( int k = 0; k < n-1; k += 4 )

{ uf.union(k, k+1); uf.union(k+2, k+3); uf.union(k, k+3); }

for ( int k = 0; k < n-1; k += 16 )

{ uf.union(k, k+4); uf.union(k, k+8); uf.union(k, k+12); }

uf.union(0, 16); uf.union(0, 32); uf.union(0, 48);

uf.displaySubsets( ); // Test 3(c)

}

DS & A Disjoint Set Union Algorithms Slide # 6

What to submit? One zipped file containing:

❏ The three modified java classes ➺ Only source code (three updated *.java files, without *.class files).

❏ A PDF document containing the NINE results from displaySubsets( ) ➺ 1(a), 1(b), 1(c), 2(a), 2(b), 2(c), 3(a), 3(b) and 3(c) ➺ Along with the Nine graphical presentations corresponding to the “tree” representations of

the above NINE test results. ➺ CLEARLY ANNOTATE each of the resulting nine arrays and their corresponding diagrams.

❏ A short report, 1-2 TYPED pages, double space, font size 12: ➺ Campare the results of the three algorithms on tests (a), (b) and (c). ➺ Focus on time efficiency and asymptotic bounds.

Put the files that you need to submit in a folder, then compress (zip) that folder!