A1 Theory W2 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 high-level description of a data structure and the operations that can be performed on it without specifying the implementation details. It defines a set of values and operations that can be applied to those values, without revealing the underlying implementation. ADT provides a conceptual framework for dealing with data structures.
A data type refers to the classification of values based on their attributes and the operations that can be performed on them. Data types are more closely tied to the programming language and its low-level implementation. Python has data types of integers, floats, strings, lists, dictionaries and more. These data types define how the values are stored in memory and what operations can be performed on them.
An abstract data type in python is a Stack: The ADT follows the LIFO principle. It can be thought of as a collection of elements with two main operations: push and pop. The ADT does not define how these operations are implemented, just what they do.
A data type in python is a List: this built in data type is a collection of values of any type. Lists allow you to store multiple elements and perform various operations on them like adding elements, removing elements, accessing elements by index and more. The data type specifies how the elements are stored in memory and how the operations are performed.
In summary, abstract data types provide a high-level description of data structures and their behaviours, while data types in programming languages like Python define how data is stored and manipulated in memory.
In your own words, what is the key idea behind abstract data types? Why are they used?
ADT’s focus on the behaviour and operations associated with data structures, rather than the specific details of how those operations are implemented or how the data is stored internally.
ADT’s are used to encapsulate the essential characteristics of a data structure and it’s interactions which allows programmers to work with complex data structures without needing to understand their intricate inner workings.
1, Modularity: defining a clear interface and operations for a data structure, changes in the implementation details can be changed without affecting the rest of the code.
2, Abstraction: Hiding the complexity of the underlying implementation helps simplify programming tasks and makes it easy to understand.
3, Code reusability: consistent interface means ADTs can be used across different projects or in the same project.
4, Specification and documentation: ADTs serve as specifications for data structures making it easier to communicate and document howe they should be used and behave.
5, Security and stability: ADTs can help prevent unintended misuse of data structures by constraining access to only specified operations.
6, Algorithm development: ADTs allow programmers to develop algorithms using a higher-level understanding of data structures.
7, Collaboration: ADTs provide a shared understanding of how data structures should be used, facilitating collaboration and reducing the likelihood of misunderstandings.
Is there a difference between capacity and length for an ADT implemented with an array?
Yes, the capacity of the array is the amount of elements it can hold and the length of an array is the amount of elements currently stored in the array.
The capacity remains constant until it is explicitly resized while the length keeps track of the actual number of elements.
Briefly describe Stack ADT giving details about
Main property of a Stack ADT
Key operations of the Stack ADT
Name a few applications where stacks are of use
Thew main property of a stack ADT is that it follows the LIFO principle. The last element added to the stack is the first one to be removed.
Keep operations of Stack ADT:
Stack: creates a stack
Push: adds an element to the top of the stack
Pop: removes the top element from the stack
Peek: Allows user to see what element is on top of the stack without removing the element
1, Function call management: manage function calls and local variables. When a function is called, its variables are pushed onto a stack and when the function returns, they are popped off. Eg, when going through code line by line
2, Arithmetic expressions: Stacks are essential in evaluating these. They can be used to convert infix notation to postfix or prefix. E.g. Polish prefix notation.
3, Undo functionality: many software applications use stacks for undo functions. Pushing an action onto the stack as it is performed to be the first action deleted off the stack if undone.
4, Browser history: Stacks are used to keep track of browser history. Pushing the last page visited onto the stack making it accessible to go backwards and forwards.
5, Balancing symbols: stacks are used when balancing symbols in programming languages. They are pushed onto the stack and when the closing symbols are encountered, they are pushed off.
What is the best-case and worst-case complexity of operations push() and pop() for a Stack ADT, if implemented with an array? No explanation no marks.
Both push and pop and a best/worst case of O(1).
Push: Best case is adding an element to the top involves accessing the next available position in the array. Worst case of adding an element to the stack still takes constant time even if the stack is at max capacity.
Pop: Best case is removing the top element from the stack which involves accessing the last added element in the array. Worst case is removing the the top element still takes constant time regardless of the amount of elements in the stack.
Both actions only involve direct access to the top of the stack.
Briefly describe Set ADT, giving details about
How one can implement the Set ADT
The main properties of the Set ADT
The key operations on the Set ADT
A set ADT represents a collection of unique elements, where each element occurs only once in the set. Sets do not maintain any particular order for their elements and they are used to store distinct values without duplicates.
There are various ways to implement a set ADT, each with different trade offs. Common implementations include using arrays, linked lists, binary search trees, hash tables and more. Thew choice of implementation depends on factors such as the expected size of the set, the frequency of insertions and lookups, and memory efficiency.
Main operations include:
1, Uniqueness: A set does not allow duplicate elements.
2, No order: The elements in a set do not have a particular order or sequence.
Key operations include:
Create the set (Set)
– Add an element to the set (add)
– Remove an element from the set (remove)
– Check if an item is a member of the set (member)
– Calculate a union, intersection, difference of two sets
Briefly describe a bit-vector, giving details about
How a bit-vector can represent a set of elements
What kind of elements can be represented this way
Explain how bitvector-based sets operate
Give an example
A bit-vector AKA a bitset, is a data structure that uses a fixed sequence of bits to represent a set of elements. Each bit in the bit-vector corresponds to an element.
Each bit position in thew bit-vector corresponds to a possible element in the universe. When an element is present in the set, the corresponding bit is set to 1, otherwise it’s set to 0.
Bit-vectors are suitable for representing sets where elements can be efficiently mapped to non-negative integers. They are well-suited for dealing with discrete elements like integers or characters.
Bit-vector based sets operate through initialization, adding an element to the set, removing an element from the set and checking for an element in the set by evaluating the corresponding bit.
Eg: we want to represent a set of integers from 0 to 15 using a bit-vector. Bit-vector is initialised to 16 bits all set to 0.
0000000000000000
Add 3:
0000000000001000
Add 6:
0000000001001000
Now we can check if 3 and 6 are in the set by looking to see if their bit is set to 1 or not. We see that it is.
If we look for 12 in the set, we see that the bit is 0, meaning 12 is not in the set.
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.
Advantages of Array-based set ADT:
1, Flexibility: array based sets can store elements of any data type, making them versatile.
2, Dynamic size: Arrays can dynamically grow or shrink as elements are added or removed, adapting to the number of elements in the set.
3, Ordered iteration: Elements in an array-based set maintain their insertion order, allowing for ordered iteration if needed.
4, Complex elements: Arrays can store complex objects with multiple attributes.
Disadvantages of Array-based:
1, Memory usage: Array-based sets consume more memory due to the need to store individual elements along with potential overhead for dynamic resizing.
2, Slower operations: Insertion, deletion and membership testing can take linear time O(n) in the worst case when searching for elements.
3, Searching: Finding an element requires iterating through the array linearly, leading to slower searches as the size of the array increases.
Advantages of Bit-vector-based Set ADT:
1, Memory efficiency: Bit-vectors are memory efficient, using only a few bits per element. Especially useful for large universes of small integers.
2, Fast operations: Bity-vector sets provide provide constant time O(1)
insertion, deletion and membership testing.
3, Compact representation: Bit-vectors are compact, requiring less memory overhead compared to arrays storing full elements.
4, Set operations: Bit-vectors enables efficient set operations like union, intersection and difference using bitwise logical operations.
Disadvantages of Bit-vector-based Set ADT:
1, Limited universe: Bit-vector sets are only suitable for elements that can be mapped to non-neg integers within a fixed range.
2, Unordered: Bit-vector sets do not inherently maintain the order of elements, which can be a disadvantage when ordered iteration is necessary.
3, No complex elements: Bit-vectors are best suited for simple elements like booleans or integers.
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()
Add:
Best-case complexity is O(1) - if element is not already in the set, it can be added to the end of the array in constant time.
Worst-case complexity is O(n) - if if the element being added is already in the set, the implementation needs to search through the entire array to search the element is not duplicated.
Remove:
Best-case is O(1) - if the element being removed is at the beginning or known index in the array, can be removed constant time.
Worst-case is O(n) - if the element to be removed is at the end of the array or needs to be searched for, it may require traversing the entire array.
Length:
Best-case is O(1) - regardless of the number of elements in the array, finding the length involves a direct look up that can be done in constant time.
Worst-case is O(1) - finding the length of the array is a constant-time operation.
Union:
Best-case is O(n) - if one of the arrays are significantly smaller thew operation involves iterating through that array and adding the elements to the other.
Worst-case is O(n^2) - if both arrays are comparable size and contain distinct elements, the operation involves checking each element in the first array against each in the second array.
Intersection:
Best-case is O(n) - if one of the arrays are significantly smaller thew operation involves iterating through that array and adding the elements to the other. This process takes linear time relative to the size of the smaller array.
Worst-case is O(n^2) - if both arrays are comparable size and contain distinct elements, the operation involves checking each element in the first array against each in the second 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:
Best-case is O(1) - adding an element involves setting a single bit-vector which can be done constant.
Worst-case is O(1) - adding an element to the set takes constant time.
Remove:
Best-case is O(1) - removing an element involves clearing a single bit-vector which is done constant time.
Worst-case is O(1) - same as best-case, done in constant time.
Length:
Best-case is O(1) - regardless of the number of elements, finding the length involves counting the number of set bits in the bit-vector which can be done constant time.
Worst-case is O(n) - when all the bits in the bit-vector are set counting the set bits requires scanning through the entire bit-vector which is linear time. Relative to the size of the bit-vector.
Union:
Best-case complexity is O(n) - if the two bit-vectors bewing combined have little difference, the resulting union operation involves a bitwise or operation on corresponding bits and can be done in linear time.
Worst-case is O(n) - If the two bit-vectors are are completely different, the union still involves a linear number of bitwise or operations.
Intersection:
Best-case complexity is O(n) - if the two bit-vectors bewing combined have little difference, the resulting intersection operation involves a bitwise or operation on corresponding bits and can be done in linear time.
Worst-case is O(n) - If the two bit-vectors are are completely different, the intersection still involves a linear number of bitwise or operations.
