CS 371: Disjoint Set Class Idea Implementation (1.5 Points)

Developed by Professor Tralie and Professor Mongan.

---

Exercise Goals

The goals of this exercise are:

1. To manipulate variables and types in python
2. To apply arithmetic expressions in python

Fill in the find method in the bubble set implementation of disjoint sets below.

Enter your Ursinus netid before clicking run. This is not your ID number or your email. For example, my netid is ctralie (non Ursinus students can simply enter their name to get this to run, but they won't get an e-mail record or any form of credit)

Netid

Clicking Run below will check your work and, if it passes, will submit your work automatically. If you are not on the campus network, you must be connected to the VPN for submission to be successful! You will receive a copy of your code via e-mail, so you'll know that it was submitted if you receive that e-mail! VPN access requires Multi-Factor Authentication, which sends you a code when you log into the network. Instructions on configuring these for your account can be found here.

Student Code

# List of lists, where each inner list corresponds to a bubble class MyDisjointSet: def __init__(self, N): self.N = N self._bubbles = [] for i in range(N): self._bubbles.append({i}) def _find_i(self, i): """ Find the index of the bubble that holds a particular value in the list of bubbles Parameters ---------- i: int Element we're looking for Returns ------- Index of the bubble containing i """ index = -1 k = 0 while k < len(self._bubbles) and index == -1: if i in self._bubbles[k]: index = k k += 1 return index def find(self, i, j): """ Return true if i and j are in the same component, or false otherwise Parameters ---------- i: int Index of first element j: int Index of second element """ return False #TODO: This is a dummy value def union(self, i, j): """ Merge the two sets containing i and j, or do nothing if they're in the same set Parameters ---------- i: int Index of first element j: int Index of second element """ idx_i = self._find_i(i) idx_j = self._find_i(j) if idx_i != idx_j: # Merge lists # Decide that bubble containing j will be absorbed into # bubble containing i self._bubbles[idx_i] |= self._bubbles[idx_j] # Remove the old bubble containing j self._bubbles = self._bubbles[0:idx_j] + self._bubbles[idx_j+1::]

Test Code Block

# Run some tests on the class s = MyDisjointSet(10) s.union(0, 2) s.union(1, 8) s.union(8, 7) print(s.find(0, 3), end='.') print(s.find(1, 7), end='.') s.union(1, 6) s.union(0, 1) print(s.find(0, 7), end='.') print(s.find(1, 9))

Output

---