Bag

Question 1

What is an ADT Bag?

Answer 1

A container.

The elements are not unique & they do not have positions the order of the elements is not important.

There are
- no positions
- no operations that take a position as a parameter or that return a position
- the added elements are not necessarily stored in the order in which they
were added (they can be stored in this way, but there is no guarantee, and we
should not make any assumptions regarding the order of the elements)

Question 2

What is the representation for an ADT Bag?

Answer 2

Can be represented using several data structures,
one of them is a dynamic array.

Independently of the chosen data structure,
there are two options for storing the elements:

(R1) store separately every element that was added
(R2) store each element only once and keep a frequency count for it

Dynamic Array specific representations:

(R3) store the unique elements in a dynamic array and store separately the positions from this array for every element that appears in the Bag

(R4) if the elements of the Bag are integer numbers,
the positions of the array can represent the elements & the value from the position is the frequency of the element,
thus, the frequency of the minimum element is at position 1 (assume 1-based indexing)

Question 3

What is the domain of an ADT Bag?

Answer 3

ADT Bag Domain

B = { b | b is a Bag with elements of the type TElem}

Question 4

What are the operations on an ADT Bag?

Question 5

What is the ADT Bag Iterator?

Question 6

What is an ADT Sorted Bag?

Answer 6

An ADT Bag.

The elements are sorted based on a relation.

Usually there are two approaches, when we want to order elements:

• Assume that they have a natural ordering, and use this ordering
  (for ex: alphabetical ordering for strings, ascending ordering for numbers, etc)
• Sometimes, we want to order the elements in a different way than the natural
  ordering (or there is no natural ordering) ⇒ we use a relation
  A relation will be considered as a function with two parameters
  (the two elements that are compared)
  which returns true if they are in the correct order,
  or false if they should be reversed.

Question 7

What is the representation for an ADT SortedBag?

Answer 7

Can be represented using several data structures,
one of them being the dynamic array.

Independently of the chosen data structure,
there are two options for storing the elements:
(R1) store separately every element that was added
(in the order given by the relation)
(R2) store each element only once (in the order given by the relation)
and keep a frequency count for it

Question 8

What is the domain of an ADT SortedBag?

Answer 8

Domain

SB = { sb | sb is a sorted bag that uses a relation to order the elements }

Question 9

What are the operations on an ADT SortedBag?

Question 10

What is the ADT SortedBag Iterator?

Question 11

ADT Bag vs ADT SortedBag

Answer 11

Modification in the interface:

• for a SB, the init operation receives a relation as a parameter

- for a SB, the iterator has to return the elements in the order given by 
  the relation (the iterator operations should have a Θ(1) complexity), 
  so internally the elements have to be stored based on the relation