- 2 Implementations Of Set Operations Consider The Implementation Of A Mathematical Set That Supports The Functions Ins 1 (259.31 KiB) Viewed 113 times
2. Implementations of Set Operations. Consider the implementation of a mathematical set¹ that supports the functions InsertSingleElement, IsMember, Union, and InPlace Union. 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: 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 unchanged Adding 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) ¹https://en.wikipedia.org/wiki/Set_(mathematics)
Union creates a new UnorderedSet that contains the union of two sets: S1 UnorderedSet ({1, 2, 3, 4}) 5, 7} S2 = UnorderedSet({3, S3 Union (S1, S2) #Now S3 is {1, 2, 3, 4, 5, 7} and S1 and S2 are unchanged Union InPlace 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.