CSC 1061 Data Structures: Bag (Static Array)

Static arrays are fixed-size data structures, declared at compile time and stored on the stack. Their size cannot change during runtime.

A specialized way of organizing and storing data in computers to efficiently perform operations on that data.

Big-O notation estimates an algorithm's efficiency in terms of execution time, independent of the specific program or computer.

A collection of elements that can be accessed through an index, with elements of the same data type.

A data structure that allows elements to be added and removed without maintaining any specific order. Elements can be duplicated.

A statement that must be true for a data structure to be considered valid. These statements help to define the correct state of the data structure.

A fixed-size array that stores data elements of a specific type. The size of the array is set at compile time, and its elements must be accessed using valid indices to avoid errors.

An abstract data type (ADT) that defines operations (like adding, removing, and checking for elements) that can be applied to a Bag data structure.

A data member that keeps track of the number of elements currently stored in the data structure. It's initialized to zero, indicating an empty structure. It's incremented when adding elements and decremented when removing them.

A member function that adds a new element to the data structure. It ensures the new element is successfully added before returning a boolean value indicating success or failure.

A member function that provides the number of elements currently stored in the data structure. It doesn't modify the structure and returns an integer representing the count.

An overloaded operator used for accessing and modifying elements in the data structure, similar to accessing elements in an array. It acts as both a getter and setter.

A Bag Data Structure is an unordered collection of values that may have duplicates. Bags do NOT care about order and are described like a Bag of groceries.

A container is a holder object that stores a collection of other objects (elements). The container manages the storage space for its elements and provides member functions to access and modify the collection.

A Bag is a limited (fixed size), unordered data structure. All data structures start out empty (zero elements). Bags must keep track of the number of elements in the Bag (data member: size).

The time complexity of an algorithm is a measure of how long it takes to run as a function of the input size. Big O notation provides a way to express the time complexity in a concise way.

Constant time complexity means the runtime of the algorithm is independent of the input size. It always takes the same amount of time, regardless of how much data you have.

A logarithmic time complexity means the runtime grows proportionally to the logarithm of the input size. This means the algorithm becomes slightly slower as the input size increases, but not as drastically as linear time.

Linear time complexity means the runtime grows directly proportional to the input size. This means the algorithm becomes slower as the input size increases, but at a predictable rate.

Quadratic time complexity means the runtime grows proportionally to the square of the input size. This means the algorithm becomes significantly slower as the input size increases, and the performance can degrade quickly.

Creating an empty Bag is a constant time operation because it involves setting up the data structure with no initial elements. The time is independent of the input size.

Adding an item to an unordered Bag is a constant time operation because it involves inserting the item at any available position. The time is independent of the number of elements already in the Bag.