U3 AOS1: ADTS & Graphs Flashcards
Define ADTS
An abstract data type is a data structure and its allowable operations
Define sets
A collection of unordered and unique elements
Define arrays
A collection of elements of the same data type and a fixed length
Define lists
A collection of elements of any data type and a variable length (able to be appended or removed)
What are primitive operations?
Operations that
create, destroy, inspect, observe, or change the data structure
What are dictionaries
Unordered collection of {key,value} pairs, where the key is unique
What is a linked list?
A sequential access data structure, where each element can be accessed only in particular order.
What is a data structure and why are they useful?
A data structure is a particular way of organising the data so that it can be used efficiently. They provide a means to managing large amounts of data efficiently through algorithms.
What is an ADT
Combination of a data structure and its allowable operations
What does contiguous mean?
Adjacent to, neighbouring, touching
What is the role of arrays in data modelling?
They provide efficient access to elements by index, making them suitable for scenarios where fast random access is required.
They are useful for modelling fixed size elements, such as a book with its fixed number of pages. Other examples include coordinates
However, their fixed size is not suitable for situations where the size of the data can be changing/large
Role of lists in data modelling
Since arrays are not suitable for when the size of the data may be changing, lists allow for efficient insertion and removal of elements, making them useful for
1) task management
2) scheduling,
3) data processing
They are also used to model collections of similar information (such as friends invited for a party)
Roles of Sets in data modelling
They are useful when collecting SIMILAR unique objects, such as {Monday, Tuesday, wednesday} however they don’t allow for duplicate items
Roles of Dictionaries in data modelling
- They store key-value pairs, allowing efficient retrieval of values based on keys. They provide operations for insertion, deletion, and retrieval based on keys.
- If you need to quickly retrieve values based on known keys without iterating through the entire collection
Roles of Queues & Priority queues in data modelling
As they use the FIFO principle, they are particularly useful when we want the elements in a specific order. They are used largely in scheduling problems and project management.
Priority queues are used in hospitals (based of patient condition), or a airport runway
Roles of Graphs in data modelling
Graphs are used for modelling complex relationships, or connections between specific nodes and edges, such as social networks and organisational structures.
What is meant by modularising algorithms?
Grouping part of the algorithm into smaller algorithms (modules)
Advantages of modularising algorithms
- Re-use modules in other places
- Easier to rewrite the modules
- Use a function before you have defined it
What is top-down design?
Breaking the problem down into smaller parts
- Vision → Design → Develop
Advantages of Top-down design:
-Breaking down the problem helps clarify the problem
- At each step of refinement, the new parts become easier to figure out
- Reusable parts
- Allows more than one person to work on the solution
What principle do stacks use?
LIFO (last in, first out) or (FILO), just think of stack of plates for dishwashing
What is morse code?
Morse code is a method that is used to encode letters of the alphabet, numbers, and punctuation marks as arrangements/sequences of 2 different “signals”, known as “dots” and “dashes”
For real-world problems, what ADT should you use when the number of items is fixed?
Arrays, and if it isn’t fixed then Lists
For real-world problems, what ADT should you use when the order of the items doesn’t matter?
A Set
Define Paths
Sequences of vertices that are connected so that we can move from A to B
Define forests
A graph that has no cycles but is not necessarily connected
What are simple graphs?
Only have a single edge between any pair of vertices and no loops
What are circuits?
A graph contains a circuit if there is more than one path that connects two nodes
What are walks?
A walk is a sequence of edges, each edge connecting successive nodes
What are trails?
A trail is a walk with no repeated edges.
What is a cycle
A path that starts and ends on the same node
What is a binary search tree?
A binary tree where every node in the left subtree is less than the root, and every node in the right subtree is greater than the root
How does insertion work in a binary search tree
The new element is compared with the current node’s value. If the element is less than the node’s value, it is inserted to the left of the subtree, if it is greater, it is inserted to the right
Complete Graphs
Every node is adjacent to every other vertex
Degree (No. of edges incident to a vertex) = ∣V∣−1
Number of edges = V(V-1)/2
