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 multi-dimensional arrays (or equivalent)

Content

Additional information

Use arrays (or equivalent) in the design of solutions to simple problems.

A one-dimensional array is a useful way of representing a vector. A two-dimensional array is a useful way of representing a matrix. More generally, an n-dimensional 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 (non-text) file.

 

4.2.1.4 Abstract data types/data structures

Content

Additional information

Be familiar with the concept and uses of a:

  • queue
  • stack
  • graph
  • tree
  • hash table
  • dictionary
  • vector.

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 built-in 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:

  • queues (linear, circular, priority)
  • stacks
  • hash tables.
 

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:

  • add an item
  • remove an item
  • test for an empty queue
  • test for a full queue.
 

4.2.3 Stacks

4.2.3.1 Stacks

Content

Additional information

Be able to describe and apply the following operations:

  • push
  • pop
  • peek or top
  • test for empty stack
  • test for stack full.

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:

  • graph
  • weighted graph
  • vertex/node
  • edge/arc
  • undirected graph
  • directed graph.
 

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 parent-child 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 key-value 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:

  • [2.0, 3.14159, -1.0, 2.718281828]
  • 4-vector over ℝ written as ℝ4
  • function interpretation
    • 0 ↦ 2.0
    • 1 ↦ 3.14159
    • 2 ↦ -1.0
    • 3 ↦ 2.718281828
    • ↦ means maps to

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 co-domain, ℝ, the set of Reals

For example, in Python the 4-vector 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 2-vector over ℝ would be written as [2.0,3.0].

1-D array representation of a vector.

For example in VB.Net, a 4-vector over ℝ would be written as Dim example(3) As Single.

Visualising a vector as an arrow.

For example a 2-vector [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 scalar-vector multiplication.

Know that vector addition achieves translation and scalar-vector 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 = [u1, …., un ] and v = [v1, ….., vn ] is

uv = u1v1 + u2v2 + …… + unvn

Applications of dot product.

Finding the angle between two vectors.