CSCI 260 Fall 2026: Lab 2: Union Find: Heuristics for faster performance


Due: September 29, 2026 11:59 pm

Task: You are to modify your Union-Find implementation from Lab 1 to use path compression and union-by-size; this consititutes the quick-union version of union-find. The executable should be called testappQU ("Quick-Union") to differentiate it from your initial testappUF.

  1. Use git to make the Lab2 directory.
  2. Copy all the .cpp files, .h files, gen, the makefile, and some test files from the Lab1 directory to the Lab2 directory.
  3. cd into the Lab2 directory and change the name of the unionfind.cpp file to unionfindQU.cpp
  4. edit the makefile so that the executable is now called testappQU. If you are using gedit, make sure the setting for tabs (at bottom of window) is not on "use spaces" when you edit your makefile.
    Your new makefile could look like this:

    testappQU: testappUF.o unionfindQU.o
      g++ -o testappQU testappUF.o unionfindQU.o

    testappUF.o: unionfind.h testappUF.cpp
      g++ -c testappUF.cpp

    unionfindQU.o: unionfind.h unionfindQU.cpp
      g++ -c unionfindQU.cpp

    If you are new to makefiles, read up on them a little in your browser; this tutorial may be a good place to start. The thing to remember is that makefiles are very sensitive to the types of white space that are used -- tab must appear before any command (the first line of each couplet above is a list the dependencies; the second line is a command). A makefile is a place to write all the directions for how to make an executable out of code files in the current directory. To invoke the makefile in a given directory, you just invoke the command "make" while in that directory.

    5. Notice that both unionfind.cpp and unionfindQU.cpp use the same header file. That is because they present the same interface. Also, there is no need to change the test program.



How to code the new implementation:

  1. Union-by-Size

    At initialization, every element is in a singleton set and has size 0.
    When two sets are merged (unioned), if they are of different size, the greater size root is the new root, and the size of the root is updated. It is no longer necessary to ensure that the name of the set is the set of the first argument in the union (merge) command. We have to throw that convention out the window when we start doing union-by-size.
    When two sets are merged, then the larger one becomes the new root. Its new size is the sum of the sizes of the two trees; these values are stored in the 'rank' array. By convention, let the first parameter be the new root if they are tied in size (rank). Use the array "rank" that is in the unionfind.h header file for the size.

  2. Path-compression

    Each time you do a find(i), compress the path from the node i, so that every node on the path from i to i's root now has as its parent node the root of the tree. The find operations performed in the "union" procedure should also involve path-compression.

  3. Debugprint

    Alter "debugprint" so that it first outputs the parent array as is, then does a sequential set print -- i.e., prints out output such as: [3] 0 3 5 7
    [6] 4 6 9
    [8] 1 2 8 10
    That is, it prints out, in increasing order of set-name, the name of the set in square brackets, then all the elements in that set in increasing order. You may have done this as the optional part of Lab 1. If so, the same subroutine (function) will not necessarily work here. Why not? However, if you have programmed your "find" properly, then all that needs to be done in your debugprint is, after you have printed out the contents of the parent array, execute the following loop before you do the set print:
    for (int k=0; k find(k);


    Then you execute the loop that you may have used in Lab1; that is, execute a loop over all the indices from 0 to n-1, and check if parent[i]==i, in which case you would loop through the indices from 0 to n-1 checking to find the elements in the same set as i. Why does it work now, but if you left out the above "find" loop, it wouldn't work?
    Your algorithm should take no more than O(n2) * time to execute a find operation.
    Note that all the files end in "d", for debugprint. This is for testing, and should be left in your executable. However, once you have debugged the programs and if you are interested in comparing testappUF and testappQU for speed, you should remove the "d" from the end of each file; debugprint is not part of our running time calculations of interest.