Answer Happy

2. Implementations of Set Operations. Consider the implementation of a mathematical set 1 that supports the functions InsertSingleElement, IsMember, Union, and InPlaceUnion. There are many ways to implement a mathematical set data structure. Two of the most obvious ways are as a sorted array or as an unsorted linked list. The constructor UnorderedSet initializes an empty list: S= UnorderedSet () # Set 'S' is now the empty set \{\} We can also use UnorderedSet to initialize a set with a list or as a copy constructor: Adding an element one-by-one: S1 = UnorderedSet ({1,2,3,4,5}) # S1 is now {1,2,3,4,5} S2 = UnorderedSet (S1) # S2 is now {1,2,3,4,5} and S1 is unche an element one-by-one: S2. InsertSingleElement ( 7) # S2 is now {1,2,3,4,5,7} S1. InsertSingleElement (2) # S1 is now {1,2,3,4,5} (unchanged) 1 https://en.w1kiped1a.org/wiki/Set_(mathematics)
Union creates a new UnorderedSet that contains the union of two sets: S1= UnorderedSet ({1,2,3,4})S2= UnorderedSet ({3,5,7}S3= Union (S1, S2)​ # Now S3 is {1,2,3,4,5,7} and S1 and S2 are unchanged UnionInPlace adds the elements of another set to the current set: S1. UnionInPlace (S2) # Now S1 is {1,2,3,4,5,7} and S2 is unchanged (a) For a sorted array implementation, write pseudocode for the above four functions. State the asymptotic complexity for each function and give a brief justification. (b) Repeat the above for an unsorted linked-list implementation of each of the four functions.