+1 (208) 254-6996 essayswallet@gmail.com
Select Page

Read the instruction and write an 1-2 pages essay. All instructions are attached. In the “union find assignment.pdf” there’s all the instruction. In the zip file, there are 9 programs I made. In the HW1. pdf, I drew a graph to indicate the results of each program, they show how each program unions. There are three big programs called quickfind, quickunion and weightquickunionfind. Each of these three programs has three different algorithms. Engineers first require to compare the efficiency and asymptotic bounds of each algorithm. Then, they compare the results from all kinds of algorithms in quickfind, quickunion and weightquickunionfind. The measure would be focusing on time efficiency and asymptotic bounds. Please write more about comparing.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

63

QuickFindUF test(a)

Result:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

63

QuickFindUF test(b)

Result:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

63

QuickFindUF test(c)

Result:

0 1 2 3 4 5 6 7 8 9 10 11 12

19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60 61 62 63

QuickUnionUF test(a)

13 14 15 16 17 18

Result

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

63

QuickUnionUF test(b)

Result:

19

18

21

23

22

20

25

27

26

24

29

31

30

28

33

35

34

32

37

39

38

36

41

43

42

40

45

47

46

44

49

48

51

50

53

55

54

52

57

59

58

56

61

63

62

60

1

3

2

5

7

6

4

9

11

10

8

13

15

14

12

17

16

0

QuickUnionUF test(c)

Result:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

0

WeightedQuickUnionUF test(a)

Result:

63 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

0

WeightedQuickUnionUF test(a)

Result:

3

WeightedQuickUnionUF test(c)

2

0

1

7

6

4

5

11

10

8

9

15

14

12

13

19

18

16

17

23

22

20

21

27

26

24

25

31

30

28

29 35

34

32

33

39

38

36

37

43

42

40

41

47

46

44

45 51

50

48

49

55

54

52

53

59

58

56

57

63

62

60

61

Result:

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!

## QuickFindUF.java

`package   UnionFind_SourceCode ;public   class   QuickFindUF   {     private   int []  id ;      // id[i] = component identifier of i     private   int  count ;     // number of components     /**     * Initializes an empty union-find data structure with     * { @code  n} elements { @code  0} through { @code  n-1}.      * Initially, each elements is in its own set.     *     *  @param   n the number of elements     *  @throws  IllegalArgumentException if { @code  n < 0}     */     public   QuickFindUF ( int  n )   {        count  =  n ;        id  =   new   int [ n ];         for   ( int  i  =   0 ;  i  <  n ;  i ++ )            id [ i ]   =  i ;     }     /**     * Returns the number of sets.     *     *  @return  the number of sets (between { @code  1} and { @code  n})     */     public   int  count ()   {         return  count ;     }       /**     * Returns the canonical element of the set containing element { @code  p}.     *     *  @param   p an element     *  @return  the canonical element of the set containing { @code  p}     *  @throws  IllegalArgumentException unless { @code  0 <= p < n}     */     public   int  find ( int  p )   {        validate ( p );         return  id [ p ];     }     // validate that p is a valid index     private   void  validate ( int  p )   {         int  n  =  id . length ;         if   ( p  <   0   ||  p  >=  n )   {             throw   new   IllegalArgumentException ( "index "   +  p  +   " is not between 0 and "   +   ( n - 1 ));         }     }     /**     * Returns true if the two elements are in the same set.     *      *  @param   p one element     *  @param   q the other element     *  @return  { @code  true} if { @code  p} and { @code  q} are in the same set;     *         { @code  false} otherwise     *  @throws  IllegalArgumentException unless     *         both { @code  0 <= p < n} and { @code  0 <= q < n}     *  @deprecated  Replace with two calls to { @link  #find(int)}.     */    @ Deprecated     public   boolean  connected ( int  p ,   int  q )   {        validate ( p );        validate ( q );         return  id [ p ]   ==  id [ q ];     }       /**     * Merges the set containing element { @code  p} with the      * the set containing element { @code  q}.     *     *  @param   p one element     *  @param   q the other element     *  @throws  IllegalArgumentException unless     *         both { @code  0 <= p < n} and { @code  0 <= q < n}     */     public   void  union ( int  p ,   int  q )   {        validate ( p );        validate ( q );         int  pID  =  id [ p ];     // needed for correctness         int  qID  =  id [ q ];     // to reduce the number of array accesses         // p and q are already in the same component         if   ( pID  ==  qID )   return ;         for   ( int  i  =   0 ;  i  <  id . length ;  i ++ )             if   ( id [ i ]   ==  pID )  id [ i ]   =  qID ;        count -- ;     }     /**     * Reads an integer { @code  n} and a sequence of pairs of integers     * (between { @code  0} and { @code  n-1}) from standard input, where each integer     * in the pair represents some element;     * if the elements are in different sets, merge the two sets     * and print the pair to standard output.     *      *  @param  args the command-line arguments     */     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)                         }     // prints out the contents of the array id[] from id[0] to id[n-1]     private   void  displaySubsets ()   {          System . out . print ( "[" );          for   ( int  i  =   0 ;  i  <  id . length ;  i ++ )   {              System . out . print ( id [ i ] + " " );          }          System . out . println ( "]\n" );     }}`

## QuickUnionUF.java

`package   UnionFind_SourceCode ;public   class   QuickUnionUF   {     private   int []  parent ;    // parent[i] = parent of i     private   int  count ;       // number of components     /**     * Initializes an empty union-find data structure with     * { @code  n} elements { @code  0} through { @code  n-1}.      * Initially, each elements is in its own set.     *     *  @param   n the number of elements     *  @throws  IllegalArgumentException if { @code  n < 0}     */     public   QuickUnionUF ( int  n )   {        parent  =   new   int [ n ];        count  =  n ;         for   ( int  i  =   0 ;  i  <  n ;  i ++ )   {            parent [ i ]   =  i ;         }     }     /**     * Returns the number of sets.     *     *  @return  the number of sets (between { @code  1} and { @code  n})     */     public   int  count ()   {         return  count ;     }       /**     * Returns the canonical element of the set containing element { @code  p}.     *     *  @param   p an element     *  @return  the canonical element of the set containing { @code  p}     *  @throws  IllegalArgumentException unless { @code  0 <= p < n}     */     public   int  find ( int  p )   {        validate ( p );         while   ( p  !=  parent [ p ])            p  =  parent [ p ];         return  p ;     }     // validate that p is a valid index     private   void  validate ( int  p )   {         int  n  =  parent . length ;         if   ( p  <   0   ||  p  >=  n )   {             throw   new   IllegalArgumentException ( "index "   +  p  +   " is not between 0 and "   +   ( n - 1 ));         }     }     /**     * Returns true if the two elements are in the same set.     *      *  @param   p one element     *  @param   q the other element     *  @return  { @code  true} if { @code  p} and { @code  q} are in the same set;     *         { @code  false} otherwise     *  @throws  IllegalArgumentException unless     *         both { @code  0 <= p < n} and { @code  0 <= q < n}     *  @deprecated  Replace with two calls to { @link  #find(int)}.     */    @ Deprecated     public   boolean  connected ( int  p ,   int  q )   {         return  find ( p )   ==  find ( q );     }     /**     * Merges the set containing element { @code  p} with the      * the set containing element { @code  q}.     *     *  @param   p one element     *  @param   q the other element     *  @throws  IllegalArgumentException unless     *         both { @code  0 <= p < n} and { @code  0 <= q < n}     */     public   void  union ( int  p ,   int  q )   {         int  rootP  =  find ( p );         int  rootQ  =  find ( q );         if   ( rootP  ==  rootQ )   return ;        parent [ rootP ]   =  rootQ ;          count -- ;     }     /**     * Reads an integer { @code  n} and a sequence of pairs of integers     * (between { @code  0} and { @code  n-1}) from standard input, where each integer     * in the pair represents some element;     * if the elements are in different sets, merge the two sets     * and print the pair to standard output.     *      *  @param  args the command-line arguments     */     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)     }     // prints out the contents of the array id[] from id[0] to id[n-1]     private   void  displaySubsets ()   {         System . out . print ( "[" );         for   ( int  i  =   0 ;  i  <  parent . length ;  i ++ )   {               System . out . print ( parent [ i ] + " " );         }         System . out . println ( "]\n" );     }}`

## WeightedQuickUnionUF.java

`package   UnionFind_SourceCode ;public   class   WeightedQuickUnionUF   {     private   int []  parent ;     // parent[i] = parent of i     private   int []  size ;       // size[i] = number of elements in subtree rooted at i     private   int  count ;        // number of components     /**     * Initializes an empty union-find data structure with     * { @code  n} elements { @code  0} through { @code  n-1}.      * Initially, each elements is in its own set.     *     *  @param   n the number of elements     *  @throws  IllegalArgumentException if { @code  n < 0}     */     public   WeightedQuickUnionUF ( int  n )   {        count  =  n ;        parent  =   new   int [ n ];        size  =   new   int [ n ];         for   ( int  i  =   0 ;  i  <  n ;  i ++ )   {            parent [ i ]   =  i ;            size [ i ]   =   1 ;         }     }     /**     * Returns the number of sets.     *     *  @return  the number of sets (between { @code  1} and { @code  n})     */     public   int  count ()   {         return  count ;     }       /**     * Returns the canonical element of the set containing element { @code  p}.     *     *  @param   p an element     *  @return  the canonical element of the set containing { @code  p}     *  @throws  IllegalArgumentException unless { @code  0 <= p < n}     */     public   int  find ( int  p )   {        validate ( p );         while   ( p  !=  parent [ p ])            p  =  parent [ p ];         return  p ;     }     /**     * Returns true if the two elements are in the same set.     *      *  @param   p one element     *  @param   q the other element     *  @return  { @code  true} if { @code  p} and { @code  q} are in the same set;     *         { @code  false} otherwise     *  @throws  IllegalArgumentException unless     *         both { @code  0 <= p < n} and { @code  0 <= q < n}     *  @deprecated  Replace with two calls to { @link  #find(int)}.     */    @ Deprecated     public   boolean  connected ( int  p ,   int  q )   {         return  find ( p )   ==  find ( q );     }     // validate that p is a valid index     private   void  validate ( int  p )   {         int  n  =  parent . length ;         if   ( p  <   0   ||  p  >=  n )   {             throw   new   IllegalArgumentException ( "index "   +  p  +   " is not between 0 and "   +   ( n - 1 ));            }     }     /**     * Merges the set containing element { @code  p} with the      * the set containing element { @code  q}.     *     *  @param   p one element     *  @param   q the other element     *  @throws  IllegalArgumentException unless     *         both { @code  0 <= p < n} and { @code  0 <= q < n}     */     public   void  union ( int  p ,   int  q )   {         int  rootP  =  find ( p );         int  rootQ  =  find ( q );         if   ( rootP  ==  rootQ )   return ;         // make smaller root point to larger one         if   ( size [ rootP ]   <  size [ rootQ ])   {            parent [ rootP ]   =  rootQ ;            size [ rootQ ]   +=  size [ rootP ];         }         else   {            parent [ rootQ ]   =  rootP ;            size [ rootP ]   +=  size [ rootQ ];         }        count -- ;     }     /**     * Reads an integer { @code  n} and a sequence of pairs of integers     * (between { @code  0} and { @code  n-1}) from standard input, where each integer     * in the pair represents some element;     * if the elements are in different sets, merge the two sets     * and print the pair to standard output.     *      *  @param  args the command-line arguments     */     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)     }     // prints out the contents of the array id[] from id[0] to id[n-1]     private   void  displaySubsets ()   {         System . out . print ( "[" );         for   ( int  i  =   0 ;  i  <  parent . length ;  i ++ )   {               System . out . print ( parent [ i ] + " " );         }         System . out . println ( "]\n" );            }}`