A-level Computer Science₇₅₁₇

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.

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.

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

Be able to read/write data from/to a binary (non-text) file.

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.

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.

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.

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.

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.

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.

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.

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 ℝ⁴
• 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:

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 = [ u ₁ , …., u _n ] and v = [ v ₁ , ….., v _n ] is

u ∙ v = u ₁ v ₁ + u ₂ v ₂ + …… + u _n v _n

Applications of dot product.

Finding the angle between two vectors.