4.2 Fundamentals of data structures
4.2.1 Data structures and abstract data types
4.2.1.1 Data structures
Content 
Additional information 

Be familiar with the concept of data structures. 
It may be helpful to set the concept of a data structure in various contexts that students may already be familiar with. It may also be helpful to suggest/demonstrate how data structures could be used in a practical setting. 
4.2.1.2 Single and multidimensional arrays (or equivalent)
Content 
Additional information 

Use arrays (or equivalent) in the design of solutions to simple problems. 
A onedimensional array is a useful way of representing a vector. A twodimensional array is a useful way of representing a matrix. More generally, an ndimensional array is a set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements. 
4.2.1.3 Fields, records and files
Content 
Additional information 

Be able to read/write from/to a text file. 

Be able to read/write data from/to a binary (nontext) file. 
4.2.1.4 Abstract data types/data structures
Content 
Additional information 

Be familiar with the concept and uses of a:

Be able to use these abstract data types and their equivalent data structures in simple contexts. Students should also be familiar with methods for representing them when a programming language does not support these structures as builtin types. 
Be able to distinguish between static and dynamic structures and compare their uses, as well as explaining the advantages and disadvantages of each. 

Describe the creation and maintenance of data within:

4.2.2 Queues
4.2.2.1 Queues
Content 
Additional information 

Be able to describe and apply the following to linear queues, circular queues and priority queues:

4.2.3 Stacks
4.2.3.1 Stacks
Content 
Additional information 

Be able to describe and apply the following operations:

Peek or top returns the value of the top element without removing it. 
4.2.4 Graphs
4.2.4.1 Graphs
Content 
Additional information 

Be aware of a graph as a data structure used to represent more complex relationships. 

Be familiar with typical uses for graphs. 

Be able to explain the terms:


Know how an adjacency matrix and an adjacency list may be used to represent a graph. 

Be able to compare the use of adjacency matrices and adjacency lists. 
4.2.5 Trees
4.2.5.1 Trees (including binary trees)
Content 
Additional information 

Know that a tree is a connected, undirected graph with no cycles. 
Note that a tree does not have to have a root. 
Know that a rooted tree is a tree in which one vertex has been designated as the root. A rooted tree has parentchild relationships between nodes. The root is the only node with no parent and all other nodes are descendants of the root. 

Know that a binary tree is a rooted tree in which each node has at most two children. 
A common application of a binary tree is as a binary search tree. 
Be familiar with typical uses for rooted trees. 
4.2.6 Hash tables
4.2.6.1 Hash tables
Content 
Additional information 

Be familiar with the concept of a hash table and its uses. 
A hash table is a data structure that creates a mapping between keys and values. 
Be able to apply simple hashing algorithms. 

Know what is meant by a collision and how collisions are handled using rehashing. 
A collision occurs when two key values compute the same hash. 
4.2.7 Dictionaries
4.2.7.1 Dictionaries
Content 
Additional information 

Be familiar with the concept of a dictionary. 
A collection of keyvalue pairs in which the value is accessed via the associated key. 
Be familiar with simple applications of dictionaries, for example information retrieval, and have experience of using a dictionary data structure in a programming language. 
Information retrieval: For example, the document 'The green, green grass grows' would be represented by the dictionary: {‘grass’ : 1, ‘green’ : 2, ‘grows’ : 1, ‘the’ : 1} ignoring letter case. 
4.2.8 Vectors
4.2.8.1 Vectors
Content 
Additional information 

Be familiar with the concept of a vector and the following notations for specifying a vector:
That all the entries must be drawn from the same field, eg ℝ. 
A vector can be represented as a list of numbers, as a function and as a way of representing a geometric point in space. A dictionary is a useful way of representing a vector if a vector is viewed as a function. f : S → ℝ the set S = {0,1,2,3} and the codomain, ℝ, the set of Reals For example, in Python the 4vector example could be represented as a dictionary as follows: {0:2.0, 1:3.14159, 2:1.0, 3:2.718281828} 
Dictionary representation of a vector. 
See above. 
List representation of a vector. 
For example, in Python, a 2vector over ℝ would be written as [2.0,3.0]. 
1D array representation of a vector. 
For example in VB.Net, a 4vector over ℝ would be written as Dim example(3) As Single. 
Visualising a vector as an arrow. 
For example a 2vector [2.0, 3.0] over ℝ can be represented by an arrow with its tail at the origin and its head at (2.0, 3.0). 
Vector addition and scalarvector multiplication. 
Know that vector addition achieves translation and scalarvector multiplication achieves scaling. 
Convex combination of two vectors, u and v. 
Is an expression of the form αu + βv where α, β ≥ 0 and α + β = 1 
Dot or scalar product of two vectors. 
The dot product of two vectors, u and v, u = [u_{1}, …., u_{n} ] and v = [v_{1}, ….., v_{n }] is u ∙ v = u_{1}v_{1} + u_{2}v_{2} + …… + u_{n}v_{n} 
Applications of dot product. 
Finding the angle between two vectors. 