Sets 1SetsSets 1SetsSets 2 Notes | EduRev

: Sets 1SetsSets 1SetsSets 2 Notes | EduRev

 Page 1


Sets 1
Sets
Page 2


Sets 1
Sets
Sets 2
Storing a Set in a List
We can implement a set with a list
Elements are stored sorted according to some 
canonical ordering
The space used is O(n)
Ø List
Nodes storing set elements in order
Set elements
Page 3


Sets 1
Sets
Sets 2
Storing a Set in a List
We can implement a set with a list
Elements are stored sorted according to some 
canonical ordering
The space used is O(n)
Ø List
Nodes storing set elements in order
Set elements
Sets 3
Generic Merging (§10.2)
Generalized merge 
of two sorted lists
A and B
Template method 
genericMerge
Auxiliary methods
? aIsLess
? bIsLess
? bothEqual
Runs in O(n
A
+ n
B
)
time provided the 
auxiliary methods 
run in O(1) time
Algorithm genericMerge(A, B)
S ? empty sequence
while ¬A.isEmpty()  ? ¬B.isEmpty()
a ? A.first().element();  b ? B.first().element()
if a < b
aIsLess(a, S);  A.remove(A.first())
else if b < a
bIsLess(b, S);  B.remove(B.first())
else { b = a }
bothEqual(a, b, S)
A.remove(A.first());  B.remove(B.first())
while ¬A.isEmpty()
aIsLess(a, S);  A.remove(A.first())
while ¬B.isEmpty()
bIsLess(b, S);  B.remove(B.first())
return S
Page 4


Sets 1
Sets
Sets 2
Storing a Set in a List
We can implement a set with a list
Elements are stored sorted according to some 
canonical ordering
The space used is O(n)
Ø List
Nodes storing set elements in order
Set elements
Sets 3
Generic Merging (§10.2)
Generalized merge 
of two sorted lists
A and B
Template method 
genericMerge
Auxiliary methods
? aIsLess
? bIsLess
? bothEqual
Runs in O(n
A
+ n
B
)
time provided the 
auxiliary methods 
run in O(1) time
Algorithm genericMerge(A, B)
S ? empty sequence
while ¬A.isEmpty()  ? ¬B.isEmpty()
a ? A.first().element();  b ? B.first().element()
if a < b
aIsLess(a, S);  A.remove(A.first())
else if b < a
bIsLess(b, S);  B.remove(B.first())
else { b = a }
bothEqual(a, b, S)
A.remove(A.first());  B.remove(B.first())
while ¬A.isEmpty()
aIsLess(a, S);  A.remove(A.first())
while ¬B.isEmpty()
bIsLess(b, S);  B.remove(B.first())
return S
Sets 4
Using Generic Merge 
for Set Operations
Any of the set operations can be 
implemented using a generic merge
For example:
? For intersection: only copy elements that 
are duplicated in both list
? For union: copy every element from both 
lists except for the duplicates
All methods run in linear time.
Page 5


Sets 1
Sets
Sets 2
Storing a Set in a List
We can implement a set with a list
Elements are stored sorted according to some 
canonical ordering
The space used is O(n)
Ø List
Nodes storing set elements in order
Set elements
Sets 3
Generic Merging (§10.2)
Generalized merge 
of two sorted lists
A and B
Template method 
genericMerge
Auxiliary methods
? aIsLess
? bIsLess
? bothEqual
Runs in O(n
A
+ n
B
)
time provided the 
auxiliary methods 
run in O(1) time
Algorithm genericMerge(A, B)
S ? empty sequence
while ¬A.isEmpty()  ? ¬B.isEmpty()
a ? A.first().element();  b ? B.first().element()
if a < b
aIsLess(a, S);  A.remove(A.first())
else if b < a
bIsLess(b, S);  B.remove(B.first())
else { b = a }
bothEqual(a, b, S)
A.remove(A.first());  B.remove(B.first())
while ¬A.isEmpty()
aIsLess(a, S);  A.remove(A.first())
while ¬B.isEmpty()
bIsLess(b, S);  B.remove(B.first())
return S
Sets 4
Using Generic Merge 
for Set Operations
Any of the set operations can be 
implemented using a generic merge
For example:
? For intersection: only copy elements that 
are duplicated in both list
? For union: copy every element from both 
lists except for the duplicates
All methods run in linear time.
Sets 5
Set Operations
We represent a set by the 
sorted sequence of its 
elements
By specializing the auxliliary 
methods he generic merge 
algorithm can be used to 
perform basic set 
operations:
? union
? intersection
? subtraction
The running time of an  
operation on sets A and B 
should be at most O(n
A
+ n
B
)
Set union:
? aIsLess(a, S)
S.insertFirst(a)
? bIsLess(b, S)
S.insertLast(b)
? bothAreEqual(a, b, S)
S. insertLast(a)
Set intersection:
? aIsLess(a, S)
{ do nothing }
? bIsLess(b, S)
{ do nothing }
? bothAreEqual(a, b, S)
S. insertLast(a)
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!