Advanced Algorithms

Lab #2: Ordered Set Class

Objective

During this activity, students will be able to:

IMPORTANT

For this programming assignment, students are required to complete all work independently and are not permitted to use AI-assisted tools, such as GitHub Copilot, ChatGPT, Gemini, or similar platforms, to automatically generate code. Using AI tools in this way undermines the learning process and violates academic integrity policies. The purpose of this assignment is to assess your understanding and application of the concepts covered in the course. Failure to comply with these guidelines may result in academic penalties, including but not limited to a lower grade.

If you have any questions about the assignment or need clarification on any concepts, please do not hesitate to visit your instructor during office hours. Rely solely on your own knowledge, the course materials, and any authorized resources provided by the instructor.

Description

This activity must be developed in the pre-assigned teams of two.

NOTE: The files developed so far in class for this lab are available in the course’s GitHub repository.

Starting from the code in the ordered_set.py file created in class, add the operations described below to the generic OrderedSet[T] class. Remember that an ordered set is a collection of non-repeated elements where the order of insertion is preserved and guaranteed during iteration.

Operation Description
def __init__(
    self,
    values: Iterable[T] = []
) -> None 		Initialize an new instance of this class with the elements contained in values.
def __repr__(self) -> str Called by the repr() built-in function to compute the “official” string representation of this ordered set. When the set is empty, it returns the string "OrderedSet()". When the set has one or more elements, the returned string should contain inside the parenthesis a square bracket delimited list with all its elements separated by commas, for example: "OrderedSet([1, 2, 3])".
def __contains__(
    self,
    value: T
) -> bool 		\(x \in A\)
Called by the in operator to determine if value is contained in this ordered set.
def __len__(self) -> int: \(\lvert A \rvert\)
Called by the built-in function len() to determine the number of elements (cardinality) contained in this ordered set.
def add(
    self,
    value: T
) -> None 		Add element value to this ordered set if it is not present.
def discard(
    self,
    value: T
) -> None 		Remove element value from this ordered set if it is present.
def remove(
    self,
    value: T
) -> None 		Remove element value from this ordered set. Raises KeyError if value is not contained in the set.
def __iter__(
    self
) -> Iterator[T] 		Called when an iterator is required for this ordered set. For example, in a for loop, or when calling the iter() built-in function. This method should return a new iterator object that can iterate over all the elements in this ordered set using the iterator protocol.
def __eq__(
    self,
    other: object
) -> bool 		\(A = B\)
Called by the == operator to determine if this ordered set is equal to other. Set \(A\) is equal to set \(B\) if both sets have exactly the same elements. The order of the elements does not matter.
def __le__(
    self,
    other: OrderedSet[T]
) -> bool 		\(A \subseteq B\)
Called by the <= operator to determine if this ordered set is a subset of other. Set \(A\) is a subset of a set \(B\) if all elements of \(A\) are also elements of \(B\). The order of the elements does not matter.
def __lt__(
    self,
    other: OrderedSet[T]
) -> bool 		\(A \subset B\)
Called by the < operator to determine if this ordered set is a proper subset of other. Set \(A\) is a proper subset of a set \(B\) if all elements of \(A\) are also elements of \(B\), but \(A \ne B\). The order of the elements does not matter.
def __ge__(
    self,
    other: OrderedSet[T]
) -> bool 		\(A \supseteq B\)
Called by the >= operator to determine if this ordered set is a superset of other. Set \(A\) is a supersubset of a set \(B\) if all elements of \(B\) are also elements of \(A\). The order of the elements does not matter.
def __gt__(
    self,
    other: OrderedSet[T]
) -> bool 		\(A \supset B\)
Called by the > operator to determine if this ordered set is a proper super of other. Set \(A\) is a proper superset of a set \(B\) if all elements of \(B\) are also elements of \(A\), but \(A \ne B\). The order of the elements does not matter.
def isdisjoint(
    self,
    other: OrderedSet[T]
) -> bool 		Determine if this ordered set and other are disjoint sets. Sets are disjoint if and only if their intersection is the empty set.
def __and__(
    self,
    other: OrderedSet[T]
) -> OrderedSet[T] 		\(A \cap B\)
Called by the & operator to determine the intersection of this ordered set and other. Returns a new ordered set with the elements that are common to this ordered set and other.
NOTE: The resulting elements should be in the same order as self.
def __or__(
    self,
    other: OrderedSet[T]
) -> OrderedSet[T] 		\(A \cup B\)
Called by the | operator to determine the union of this ordered set with other. Returns a new ordered set with all the elements of this ordered set and all the elements of other.
NOTE: The resulting elements should be in the same order as self and then other.
def __sub__(
    self,
    other: OrderedSet[T]
) -> OrderedSet[T] 		\(A - B\)
Called by the - operator to determine the difference between this ordered set and other. Returns a new ordered set with all the elements of this ordered set that do not belong to other.
NOTE: The resulting elements should be in the same order as self.
def __xor__(
    self,
    other: OrderedSet[T]
) -> OrderedSet[T] 		\(A \ominus B\)
Called by the ^ operator to determine the symmetric difference between this ordered set and other. Returns a new ordered set with all the elements that belong to this ordered set or to other but not to both.
NOTE: The resulting elements should be in the same order as self and then other.
def clear(self) -> None Remove all elements from the this ordered set.
def pop(self) -> T Remove and return the last element added to this ordered set. Raises KeyError if this set is empty.

Additionally:

Deliverables

Place in a comment at the top of the ordered_set.py source file the authors’ personal information (student ID and name), for example: 

#----------------------------------------------------------
# Lab #2: Ordered Set Class
# Implementation of a generic ordered set class and its
# corresponding operations.
#
# Date: 18-Sep-2024
# Authors:
#           A01770771 James Howlett
#           A01777771 Wade Wilson
#----------------------------------------------------------

Upload Instructions

To deliver the ordered_set.py file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Wednesday, September 18.