Difference between revisions of "Advanced Information Revision Notes"
(→Abstract Data Types & Dynamic vs Static) |
(→Abstract Data Types & Dynamic vs Static) |
||
| Line 25: | Line 25: | ||
With a static data structure, the size of the structure is fixed. | With a static data structure, the size of the structure is fixed. | ||
Static data structures are very good for storing a well-defined number of data items. | Static data structures are very good for storing a well-defined number of data items. | ||
| − | + | ||
===Advantage=== | ===Advantage=== | ||
*The memory allocation is fixed and so there will be no problem with adding and removing data items. | *The memory allocation is fixed and so there will be no problem with adding and removing data items. | ||
| + | *The memory is allocated in one block and is continuous | ||
*Easier to program as there is no need to check on data structure size at any point. | *Easier to program as there is no need to check on data structure size at any point. | ||
| Line 36: | Line 37: | ||
==Dynamic Data Structure== | ==Dynamic Data Structure== | ||
| − | + | Memory is allocated to the data structure dynamically i.e. as the program executes. | |
| − | + | This means the data structure is allowed to grow and shrink as the demand for storage arises. | |
| − | |||
| − | |||
| − | |||
===Advantage=== | ===Advantage=== | ||
| Line 47: | Line 45: | ||
===Disadvantage=== | ===Disadvantage=== | ||
*Because the memory allocation is dynamic, it is possible for the structure to 'overflow' should it exceed its allowed limit. It can also 'underflow' should it become empty. | *Because the memory allocation is dynamic, it is possible for the structure to 'overflow' should it exceed its allowed limit. It can also 'underflow' should it become empty. | ||
| − | * | + | *Allocated memory is fragmented so will take longer to read |
| + | *You might need to code basic functions such as checking its size or the number of items stored. | ||
==Abstract Data Structure== | ==Abstract Data Structure== | ||
Revision as of 09:58, 31 May 2022
Contents
Recursion
Arrays
An Array is a data structure that allows you to store several values of the same data type.
They are static structures.
You must declare the size of the array when it is created.
Memory for entire structure is given when created.
Single Dimension
Each value can be accessed by the element number within the sequence.
Multi Dimension
You need to specify the dimensions when created (ie 3, 3 ).
It can still only store one data type, so it could be a 2 dimensional array of Integers
To access an element you need to give the number for each dimension.
Abstract Data Types & Dynamic vs Static
Static Data Structure
With a static data structure, the size of the structure is fixed. Static data structures are very good for storing a well-defined number of data items.
Advantage
- The memory allocation is fixed and so there will be no problem with adding and removing data items.
- The memory is allocated in one block and is continuous
- Easier to program as there is no need to check on data structure size at any point.
Disadvantage
- Can be very inefficient as the memory for the data structure has been set aside regardless of whether it is needed or not whilst the program is executing.
Dynamic Data Structure
Memory is allocated to the data structure dynamically i.e. as the program executes. This means the data structure is allowed to grow and shrink as the demand for storage arises.
Advantage
- Makes the most efficient use of memory as the data structure only uses as much memory as it needs
Disadvantage
- Because the memory allocation is dynamic, it is possible for the structure to 'overflow' should it exceed its allowed limit. It can also 'underflow' should it become empty.
- Allocated memory is fragmented so will take longer to read
- You might need to code basic functions such as checking its size or the number of items stored.
Abstract Data Structure
An abstract data structure is one that is not defined by how it is implemented, it is instead defined by its functions.
So an abstract data structure could be implemented in many different ways, but each having the same functionality.
Queues
Stacks
Graphs
Graphs can be used to represent complex relationships, ie who knows who or how things are connected.
Vertex / Node
A point or location on the graph.
Edge / Arc
A connection from 1 node to another.
Weighted Graph
Edges will have a cost or value attached to it. This represents the cost or distance of using that edge.
Undirected
Edges are shown by a line. You can travel in both directions along the line.
If a node A is connected to node B, then node B is also connected to node A
Directed
Edges are shown with arrows, you can only travel in the direction of the arrow.
If a node A is connected to node B, then node B might not be connected to node A (it will be a separate arrow)
Adjacency Matrix
Used to store what is and isn't connected.
Essentially a table with the nodes across the top and down the sides.
You can enter a 1 or a weighting if the are connected.
0 if they aren't connected.
Adjacency List
Only stores what is connected.
For each node, simply list which nodes are connected.
Doesn't work for weighted graphs.
Matrix vs List
The advice is to use a matrix when you have a graph with many edges (Dense).
The advice is to use a List when you have few edges (Sparse)
Remember a list will also require additional processing to check the list of connections for a given node.
A matrix requires little processing, you can go direct to the location.
Trees
A tree is a specific type of graph.
- Must be connected
- Must be undirected
- Must have no cycles
Graph Traversal
Searching Algorithms
Sorting Algorithms
Optimisation Algorithms
Order of Complexity
Halting Problem
The halting problem asks:
‘Is it possible to write a program that can tell given any program and its inputs and without executing the program, whether it will halt?’
A method to do this for any program has been proven to not exist.
