Introduction To Algorithms
CS430

1 Instructions

Implement two algorithms

1. UNION-FIND: You must implement this data structure where

• UNION operation is done by rank

2. UNION-FIND-WITH-PATH-COMPRESSION: You must implement this data structure where

• UNION operation is done by rank and

• FIND-SET is implemented with path compression

• Illustration of design and implementation [20 %]

– You must briefly illustrate the design and implementation of the two algorithms

• Evaluation Report [40 %]

– You must report the evaluation of the two algorithms with test data

– The evaluation must include plots of running times for different values of m, n for the UNION-FIND structure

– The test data used must be included in the final submission along with the report

• Correctness [40 %]

– Code will be executed against pre-defined test cases

Input format

• First line - n (Number of elements)

• Number of UNION Operations will be n − 1

• Second line - m (Number of FIND-SET Operations)

• Next m + (n − 1) lines will either be a

1. Union operation U<space>x<space>y, where 1 ≤ x, y ≤ n

2. Find operation F<space>x, where 1 ≤ x ≤ n

Output format

• m lines for each FIND-SET operation, where each line outputs the root/representative of the set to which x belongs

– For union by rank, a node stores its rank which is an upper bound for its height.

– When a node is initialized, its rank is set to zero.

– To merge trees with roots x and y, first compare their ranks.

– If the ranks are different, then the larger rank tree becomes the parent, and the ranks of x and y do not change.

– Tie Break

∗ Let x ∈ T1, y ∈ T2

∗ If rank(T1) = rank(T2), root of T1 must be made the root of the resultant merged tree

• The input file name will be given as a command line argument with the option -i or --input [See below for example]

• Assume the file exists in the current directory where the program is located

• Output file must be named <input-file-name> output.txt [See below for example]

• Output file must be created in the current directory where the program is located

$ python3 union−f i n d . py −i t e s t 1 . t x t

$ python3 union−f i n d . py −−i n p u t t e s t 1 . t x t

1. Two separate source code files for the two algorithms that need to be imple mented

2. Report detailing the design, implementation and evaluation

3. Test case files