Union Find Review (Part 2)

What is the main purpose of the Network Propagation project?

To see how fast updates spread through a network of connected devices using Union-find.

How many random connections (pairings) are usually needed before every device gets the update, and how does that number change when N (the number of devices) grows?

The # of interactions increases as N increases, roughly following a linear trend.

 Roughly how many interactions were required for all devices to update?

It roughly took 6x the number of devices (N) in interactions for the entire network to get connected (applies mostly to large Ns; small ones are more affected by random chance).

Does the process ever 'stall'? Why or why not?

No, because random pairing ensures that all devices get connected in the end, it might take time for bigger Ns though, but it gets the job done.

Which union-find implementation is best for this situation?

Fast union with path compression because fast union works well for large datasets due to its “super-merge” ability, and path compression speeds up the process and allows for merging to be done quickly since every device would point to the root.

Describe how the simulation aspect of the project works (hint: consider the code in UnionFindSimulation class)?

We essentially go through every N value and run 7 trials in each N, finding the average # of total interactions to get a better sense of what the actual # of interactions might look like.