• To use git correctly. (FAQ and a short history of the minimal set of instructions you need).
• to implement an efficient data structure and algorithm;
• to explore the Union-Find ADT (a.k.a., Disjoint Set);
• to compile and test a C++ program under Linux;
• to use a small perl program for randomized data generation.

1. Implement the Union-Find ADT (description below. It is also called the Disjoint Sets ADT). Use the array implementation, with path-compression and union-by-rank.
2. Link it to the testapp program provided.
3. Test it on data generated by the provided perl program, and design your own input for testing.
4. Use "git" to submit the tested, debugged code for grading. You need to submit only the file unionfind.cpp

1. A testapp program
2. A C++ file with a stub for the find operation
3. A C++ header file
4. A Perl program to generate random test data.
5. A sample data file for input to the testapp

• union two sets
• find the set containing a given element.

The code you have been provided with:

Tasks

1. Generate inputs

   The testapp program will:
   • prompt for a file name
   • open the file and read the number of elements, followed by a bunch of commands of the form "f 5" and "u 7 3". As it reads each command, it will perform the indicated "find" or "merge" (union) on the union-find data structure that your program creates.
   First, let us find a way to create input files of this time at random.
   
   Here is an example of an input file, called in.11.8
   11
   u 5 7
   f 7
   f 5
   u 9 10
   f 2
   u 1 10
   u 2 8
   f 1
   d
   The first number is the number of elements. "u 5 7" means execute a "merge(5,7)" operation. "f 7" means execute a "find(7)" operation. The little perl script "gen" provided in your git repository will help you generate input files for testing. Remember to change the mode of the file so it is executable:
   chmod a+rx gen
   To invoke the perl script, use the command
   ./gen
   
   Do the following on the command line:
   ./gen 20 6
   ./gen 6 20
   What is the difference? Edit the gen file. Note that the hash sign comments out some lines of code (except the first line -- that line is necessary so that the file may be understood as a perl file -- don't change it!) You can uncomment the lines that seem to prompt the user for input, then run the instructions again. What is the first parameter in a call "gen 20 6"? What is the second parameter?
   
   To direct the output to a file, use ./gen > filenameHere You will want to comment out the user prompts for input (for easy outputting to a file) but it does require two inputs, the first is the number of elements, the second is the number of operations. Note that all the files end in "d", for debugprint.

2. Implement the Union-Find data structures and algorithms

   • Use an array data structure. The interface is given in the header file.
   • A test application is provided for you. The test application prompts the user for a file name; it then opens that file and reads the input and execute the operations given in the file.
   • Implement union-by-rank and path-compression.
     
     Initializing
     
     The first thing you will have to do is dynamically allocate an array of size n, once you have read your value n. Remember to do this by the instructions:
     parent = new int[k];
     
     In this implementation, the "parent" of an element i, parent[i], is the parent of i in the forest of union-find trees.
     for (int i=0; i<n; i++) parent[i]=i;
     
     Initialize "rank" to be 0 for each element at initialization, and update it as necessary during a union operation, which we have implemented as ``merge" so as not to overlap with reserve words in C++.
   • 
     
     find i
     
     find should return the name of the set i belongs to. TestappUF receives this information but does nothing with it; it does not even print it out. That's okay. When you are debugging, of course you can have your testapp print it out for debugging purposes, but remove such statements for your final version. Even if we don't print out the results of the find, Find operations can change the shape of our trees, so they need to be executed.
   • 
     
     union i j
     
     "union i j" should first "find(i)" and "find(j)". If the ranks of the roots are equal, always make the root of the tree of the first argument be the new root. Then perform the union.
   
   
   

3. Required: Refine your output

   
   
   The "d" option dumps the array to the screen. What would be more interesting is to see the collection of sets. For example,
   
   1: 1 3 5 6 8 10 11 12 47 48 53 56 63 68 74 96
   2: 2 4 19 20 21 23 24 25 26 27 29 30 32 37 40 41 44 45 60 64 65 66 70 73 76 92 93
   7: 7 67 75 86 89 91
   14: 14 15 16 17 18 22 33 34 38 39 49
   28: 28
   36: 36
   52: 52
   58: 58
   84: 84
   90: 90
   
   
   The elements within a set do not need to be in sorted order. To time an execution of testappUF on input and put the output to a file called out.11.8, use the command "time testappUF > out.11.8"
   
   

   Explore Experimental Results:

   
   Use the "time" option on linux to capture the experimental run-time of your algorithm, on various sizes of inputs. The sizes to report are 100 elements, 100 operations; 100 elements 1000 operations; 1000 elements 1000 operations; and 1000 elements 1000000 operations. NOTE: you should remove the "d" from the bottom of each input file before you time your program on it, as the "debugprint" function adds too much to the running time.
   
   Give estimates of the Big-O running times that are suggested by these results. Predict running times for other file sizes and check the actual running time. Disable the "union by height" function, and test on the same files for benchmarking. Does "union by height" yeild better results? Give Big-O estimates for both implementation: union by height, and union with no height heuristic. Remember to enable your union-by-height before you submit. Report these results in comments at the top of your code.

   Submit your results:

   Use "git" to submit your program. Git not accept late submissions.