Data Structures II· Homework
HW I - A Disjoint Menace
In the realm of math, a tale to weave,
A disjoint menace, be ready to perceive. Sets, they dance, yet never entwine,
A mathematical waltz, so sharp and fine.
HW I begins, a challenge takes shape, Disjoint sets arise, their paths can’t escape. No common ground, no shared delight,
In this world of math, they part ways at night.
A union they spurn, an intersection they flee, Disjoint sets, a mathematical decree.
No overlap, no point to share,
In this disjoint dance, they’re a rare pair.
A menace, you say, a mathematical feat,
A concept to conquer, no mean feat.
With Eyal Schachter and Benji Tusk in tow, Into the world of sets, together we go.
Attribution awaits at the homework’s end,
A journey through math, a message to send.
Eyal Schachter and Benji Tusk, our names declare, In the land of disjoint sets, we venture and dare!
Eyal Schachter (209792266) and Benji Tusk (650282680)
Question 1
Answer 1
Lemma
Assertion: For a set with elements, there were exactly union operations on the elements of .
Base Case: , there were at least 0 union operations.
Assumption: For , there were exactly union operations on the elements of .
Claim: For a set of size , there were exactly union operations on its elements.
Proof: Denote the number of union operations on the elements of A as .
Examine operation :
We perform a union operation on sets , so . Since they are disjoint sets, we know . It is given that , and we know (we do not work with empty sets).
Therefore, ( is an upper bound).
Let be the number of union operations on B, and similarly for C. By the induction assumption, .
Clearly . (Unioning B and C to form A)
Therefore
Now, The Real Shebang™
Claim: After union operations, there is no set holding more than elements.
Proof: Suppose (by means of negation) there exists a set A such that . By The Lemma™, , in contradiction to the assumption that only union operations occurred.
Question 2
Question 3
Answer 3
Two trees, with a height of 2, and a height of 1.
Question 4
Question 5
Answer 5
class Link:
def __init__(self, x):
self.representative = None
self.key = x
self.next = None
class LinkedList:
def __init__(self, x: Link):
x.representative = self
self.head = x
self.tail = x
self.size = 1
def MakeSet(x: int):
return LinkedList(Link(x))
def FindSet(x: Link):
return x.representative
def Union(_x: Link, _y: Link):
x = FindSet(_x)
y = FindSet(_y)
if x == y:
raise Exception("You're not allowed to do that!")
if x.size < y.size:
x, y = y, x
# X is now the larger set
x.tail.next = y.head
p = y.head
while p is not None:
p.representative = x
p = p.next