1. We have provided an implementation of the Set ADT in Chapter 1.

a) Implement a new version of the Set ADT using a sorted linked list.

b) Evaluate your new implementations to determine the worst case run time of each operation.

c) Compare the run times of your new versions of the Set ADT to the one from Chapter 1.

Set ADT from chapter 1:

# Creates a new set from the union of this set and setB.

def union( self, setB ):

newSet = Set()

newSet._theElements.extend( self._theElements )

for element in setB :

if element not in self :

newSet._theElements.append( element )

return newSet

# Creates a new set from the intersection: self set and setB.

def interset( self, setB ): newSet = Set()

for element in setB :

if element in self :

newSet._theElements.append( element )

return newSet

# Creates a new set from the difference: self set and setB.

def difference( self, setB ): newSet = Set()

for element in self :

if element not in self :

newSet._theElements.append( element )

return newSet def properSubset( self, setB ): if self.isSubsetOf( setB ): if self.__eq__(setB): return False else: return True return False def __add__(self,setB): return self.union(setB) def __mul__(self,setB): return self.interset(setB) def __sub__(self,setB): return self.difference(setB) def __lt_(self,setB): return self.isSubsetOf(setB)

def _str(self): print(self._theElements)