ADT, Stack ADT (array-based), Set ADT Flashcards
What is an abstract data type and how does it differ from data type? Give examples for abstract data type and also data type in Python.
An abstract data type is a logical concept that defines a set of values and operations on those values, without specifying how they are stored or implemented.
A data type is a concrete representation of an ADT in a programming language, such as a class or a structure. For example, a list is an ADT that defines a collection of values that can be accessed by index, and a list in Python is a data type that implements the list ADT using an array.
what is the key idea behind abstract data types? Why are they used?
The key idea behind ADTs is to separate the interface from the implementation, and to provide a high-level abstraction for data manipulation. This way, the user of an ADT does not need to know the details of how the data is stored or operated on, and the implementer of an ADT can change the underlying representation without affecting the user. ADTs are used to simplify the design and development of complex software systems, and to improve the readability, modularity, and reusability of code.
Is there a difference between capacity and length for an ADT implemented with an array?
The capacity of an ADT implemented with an array is the maximum number of elements that the array can hold, while the length of an ADT is the current number of elements that the ADT contains. The capacity is usually larger than the length, to allow for future growth of the ADT. For example, a list in Python has a capacity that is determined by the memory allocation of the array, and a length that is determined by the number of elements in the list.
What is the Main property of a Stack ADT
A stack ADT is a collection of values that follows the last-in first-out (LIFO) principle, meaning that the last value added to the stack is the first one removed from the stack. The main property of a stack ADT is that it only allows access to the top element of the stack, and does not allow random access to other elements.
Key operations of the Stack ADT
The key operations of a stack ADT are push, pop, peek, and isEmpty. Push adds a value to the top of the stack, pop removes and returns the value from the top of the stack, peek returns the value from the top of the stack without removing it, and isEmpty checks if the stack is empty or not.
Name a few applications where stacks are of use.
Some applications where stacks are of use are:
Evaluating arithmetic expressions in postfix notation
Implementing function calls and recursion in programming languages
Reversing the order of a sequence of values
Implementing undo and redo features in text editors
What is the best-case and worst-case complexity of operations push() and pop() for a Stack ADT, if implemented with an array?
The best-case and worst-case complexity of operations push and pop for a stack ADT, if implemented with an array, are both O(1)
, meaning that they take constant time regardless of the size of the stack. This is because push and pop only involve adding or removing an element from the end of the array, which can be done in one step. However, if the array is full and needs to be resized, the push operation may take O(n)
time, where n
is the number of elements in the stack, because it involves copying all the elements to a new larger array.
what is the main properties of the Set ADT?
A set ADT is a collection of values that does not allow duplicates, and does not have a specific order. The main properties of a set ADT are that it supports membership testing, meaning that it can check if a value is in the set or not, and it supports set operations, such as union, intersection, difference, and subset.
The key operations on the Set ADT
The key operations on a set ADT are add, remove, len, union, intersection, and contains.
Add adds a value to the set if it is not already present, remove removes a value from the set if it is present, len returns the number of elements in the set, union returns a new set that contains all the elements from both sets, intersection returns a new set that contains only the elements that are common to both sets, difference returns a new set that contains only the elements that are in the first set but not in the second set, subset checks if the first set is a subset of the second set, and contains checks if a value is in the set or not. A set ADT can be implemented in different ways, such as using an array, a linked list, a hash table, or a bit-vector.
bit-vector
A bit-vector is a sequence of bits, where each bit represents either 0 or 1. A bit-vector can represent a set of elements by mapping each element to a unique index in the bit-vector, and setting the bit at that index to 1 if the element is in the set, and 0 otherwise. For example, if we have a set of integers from 0 to 7, we can represent it using a bit-vector of length 8, where the i-th bit corresponds to the integer i. If the set is {0, 2, 5, 7}, the bit-vector is 10100101. The kind of elements that can be represented this way are those that have a finite and fixed range, such as integers, characters, or booleans. Bitvector-based sets operate by performing bitwise operations on the bit-vectors, such as AND, OR, XOR, and NOT, to implement the set operations. For example, to find the union of two sets, we can perform the bitwise OR operation on their bit-vectors, and to find the intersection of two sets, we can perform the bitwise AND operation on their bit-vectors.
What are the main advantages and disadvantages of an array-based implementation of the Set ADT compared to a bitvector-based implementation? State the advantages and disadvantages as separate sections for each.
The main advantages of an array-based implementation of the set ADT are:
It is simple and easy to implement
It allows random access to the elements in the set
It has a low memory overhead, as it only stores the elements in the set
The main disadvantages of an array-based implementation of the set ADT are:
It has a high time complexity for some operations, such as add, remove, and contains, which are O(n)
in the worst case, where n
is the number of elements in the set, because they involve searching the array for the element
It has a fixed capacity, which may be too large or too small for the set, and may require resizing the array when the set grows or shrinks
It does not preserve the order of the elements in the set, as it may shift the elements when adding or removing them
The main advantages of a bitvector-based implementation of the set ADT are:
It has a low time complexity for most operations, such as add, remove, len, union, and intersection, which are O(1)
or O(m)
, where m
is the length of the bit-vector, because they involve setting or clearing a bit, or performing a bitwise operation on the bit-vectors
It has a fixed and predictable memory usage, as it only depends on the length of the bit-vector, and does not require resizing
It preserves the order of the elements in the set, as it does not change the position of the bits
The main disadvantages of a bitvector-based implementation of the set ADT are:
It is complex and difficult to implement
It does not allow random access to the elements in the set, as it requires mapping the elements to their corresponding bits, and extracting the bits from the bit-vector
It has a high memory overhead, as it may waste space for unused bits, or require a large bit-vector for a large range of elements
What is the best-case and worst-case complexity of the below operations for a Set ADT, if implemented with an array? Explain the reason for the best and worst case. No explanation no marks.
add()
remove()
__len__()
union()
intersection()
The best-case and worst-case complexity of the below operations for a set ADT, if implemented with an array, are:
add(): O(1)
in the best case, when the element is not in the set and the array is not full, and O(n)
in the worst case, when the element is in the set or the array is full, because it involves searching the array for the element, and possibly resizing the array
remove(): O(1)
in the best case, when the element is at the end of the array, and O(n)
in the worst case, when the element is at the beginning of the array or not in the set, because it involves searching the array for the element, and possibly shifting the elements in the array
len(): O(1)
in both cases, because it involves returning the number of elements in the array, which can be stored as a variable
union(): O(n+m)
in both cases, where n
and m
are the number of elements in the two sets, because it involves creating a new array that contains all the elements from both arrays, and removing any duplicates
intersection(): O(n∗m)
in both cases, where n
and m
are the number of elements in the two sets, because it involves creating a new array that contains only the elements that are common to both arrays, and checking each element in one array against each element in the other array
What is the best-case and worst-case complexity of the below operations for the Set ADT, if implemented with a bit-vector? Explain the reason for the best and worst case. No explanation no marks.
add()
remove()
__len__()
union()
intersection()
add(): O(1)
in both cases, because it involves setting the bit at the index corresponding to the element to 1
remove(): O(1)
in both cases, because it involves clearing the bit at the index corresponding to the element to 0
len(): O(m)
in both cases, where m
is the length of the bit-vector, because it involves counting the number of bits that are 1 in the bit-vector
union(): O(m)
in both cases, where m
is the length of the bit-vector, because it involves performing the bitwise OR operation on the bit-vectors
intersection(): O(m)
in both cases, where m
is the length of the bit-vector, because it involves performing the bitwise AND operation on the bit-vectors
