Set

Question 1

What is an ADT Set?

Answer 1

A container.

In which:

• the elements are unique
• the order of the elements is not important (there are no positions)

Question 2

What are the representations for an ADT Set?

Answer 2

Dynamic Array specific representations:
(R3) if the elements of the set are numbers,
the elements are represented by the positions in the dynamic array &
a boolean value from that position shows if the element is in the set or not

*when indexing starts from 1,
the element in the dynamic array that is on position i:
⇒ the element at position: minimum + i − 1
⇒ position of an element e: e − minimum + 1

Question 3

What is the domain for an ADT Set?

Answer 3

Domain

S = {s|s is a set with elements of the type TElem}

Question 4

What are the operations on an ADT Set?

Question 5

What is an ADT SortedSet?

Answer 5

A Set.

The elements are ordered based on a relation.

Question 6

ADT Set vs ADT SortedSet

Answer 6

Modification in the interface:

• for a SS, the init operation receives a relation as a parameter
• for a SS, the iterator has to iterate through the elements in the order given by
  the relation, so we need to keep them ordered in the representation