4.4 Theory of computation
Abstraction and automation
Problemsolving
Content 
Additional information 

Be able to develop solutions to simple logic problems. 

Be able to check solutions to simple logic problems. 
Following and writing algorithms
Content 
Additional information 

Understand the term algorithm. 
A sequence of steps that can be followed to complete a task and that always terminates. 
Be able to express the solution to a simple problem as an algorithm using pseudocode, with the standard constructs:


Be able to handtrace algorithms. 

Be able to convert an algorithm from pseudocode into high level language program code. 

Be able to articulate how a program works, arguing for its correctness and its efficiency using logical reasoning, test data and user feedback. 
Abstraction
Content 
Additional information 

Be familiar with the concept of abstraction as used in computations and know that:

Information hiding
Content 
Additional information 

Be familiar with the process of hiding all details of an object that do not contribute to its essential characteristics. 
Procedural abstraction
Content 
Additional information 

Know that procedural abstraction represents a computational method. 
The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method  a procedure. 
Functional abstraction
Content 
Additional information 

Know that for functional abstraction the particular computation method is hidden. 
The result of a procedural abstraction is a procedure, not a function. To get a function requires yet another abstraction, which disregards the particular computation method. This is functional abstraction. 
Data abstraction
Content 
Additional information 

Know that details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects. 
Data abstraction is a methodology that enables us to isolate how a compound data object is used from the details of how it is constructed. For example, a stack could be implemented as an array and a pointer for top of stack. 
Problem abstraction/reduction
Content 
Additional information 

Know that details are removed until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved. 
Decomposition
Content 
Additional information 

Know that procedural decomposition means breaking a problem into a number of subproblems, so that each subproblem accomplishes an identifiable task, which might itself be further subdivided. 
Composition
Content 
Additional information 

Know how to build a composition abstraction by combining procedures to form compound procedures. 

Know how to build data abstractions by combining data objects to form compound data, for example tree data structure. 
Automation
Content 
Additional information 

Understand that automation requires putting models (abstraction of real world objects/phenomena) into action to solve problems. This is achieved by:

Computer science is about building clean abstract models (abstractions) of messy, noisy, real world objects or phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy. Computer science deals with putting the models into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled. 
Regular languages
Finite state machines (FSMs) with and without output
Content 
Additional information 

Be able to draw and interpret simple state transition diagrams and state transition tables for FSMs with no output and with output (Mealy machines only). 
Maths for regular expressions
Content 
Additional information 

Be familiar with the concept of a set and the following notations for specifying a set: A = {1, 2, 3, 4, 5 } or set comprehension: A = {x  x ∈ ℕ ∧ x ≥ 1 } where A is the set consisting of those objects x such that x ∈ ℕ and x ≥ 1 is true. Know that the empty set, {}, is the set with no elements. Know that an alternative symbol for the empty set is Ø. 
A set is an unordered collection of values in which each value occurs at most once. Several languages support set construction. In Python, for example, use of curly braces constructs a set: {1, 2, 3 }.  means such that. x ∈ ℕ means that x is a member of the set ℕ consisting of the natural numbers, ie {0, 1, 2, 3, 4, … }. The symbol ∧ means AND. The term ∧ x > = 1 means AND x is greater than or equal to 1. In Python, {2 ∗ x for x in {1, 2, 3 }} constructs {2, 4, 6 }. This is said to be a set comprehension over the set {1, 2, 3 } . 
Be familiar with the compact representation of a set, for example, the set {0^{n}1^{n}  n ≥ 1}. This set contains all strings with an equal number of 0 s and 1s. 
For example, {0^{n}1^{n}  n ≥ 1} = {01, 0011, 000111, 00001111, … } 
Be familiar with the concept of:

A finite set is one whose elements can be counted off by natural numbers up to a particular number, for example as: 1st element, 2nd element, …, 20th (and final) element. The set of natural numbers, ℕ and the set of real numbers, ℝ are examples of infinite sets. A countably infinite set is one that can be counted off by the natural numbers. The set of real numbers is not countable. The cardinality of a finite set is the number of elements in a set. Cartesian product of two sets, X and Y, written X x Y and read 'X cross Y', is the set of all ordered pairs (a, b) where a is a member of A and b is a member of B. 
Be familiar with the meaning of the term:

{0, 1 , 2 } ⊂ ℕ where ⊂ means proper subset of, that is ℕ contains everything in {0, 1, 2 } but there is at least one element in ℕ that is not in {0, 1, 2 }. {0, 1 , 2 } ⊆ {0, 1, 2, 3 } where ⊆ means subset of. ⊆ includes both ⊂ and =, for example {0, 1, 2, 3 } ⊆ {0, 1, 2, 3 } is also true, because {0, 1, 2, 3 } = {0, 1, 2, 3 }. A countable set is a set with the same cardinality (number of elements) as some subset of natural numbers. 
Be familiar with the set operations:

The set difference A\B (or alternatively AB) is defined by A\B = {x : x ∈ A and x ∉ B} 
Regular expressions
Content 
Additional information 

Know that a regular expression is simply a way of describing a set and that regular expressions allow particular types of languages to be described in a convenient shorthand notation. 
For example, the regular expression a(ab)* generates the set of strings {a, aa, ab, aaa, aab, aba, …}. 
Be able to form and use simple regular expressions for string manipulation and matching. 
Students should be familiar with the metacharacters:

Be able to describe the relationship between regular expressions and FSMs. 
Regular expressions and FSMs are equivalent ways of defining a regular language. 
Be able to write a regular expression to recognise the same language as a given FSM and vice versa. 
A student's ability to write very simple regular expressions and FSMs will be assessed. 
Regular language
Content 
Additional information 

Know that a language is called regular if it can be represented by a regular expression. 
Also, a regular language is any language that a FSM will accept. 
Contextfree languages
BackusNaur Form (BNF)/syntax diagrams
Content 
Additional information 

Be able to check language syntax by referring to BNF or syntax diagrams and formulate simple production rules. 

Be able to explain why BNF can represent some languages that cannot be represented using regular expressions. 
Classification of algorithms
Comparing algorithms
Content 
Additional information 

Understand that algorithms can be compared by expressing their complexity as a function relative to the size of the problem. Understand that the size of the problem is the key issue. 

Understand that some algorithms are more efficient:

Efficiently implementing automated abstractions means designing data models and algorithms to run quickly while taking up the minimal amount of resources such as memory. 
Maths for understanding Big0 notation
Content 
Additional information 

Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the codomain, for example ℕ → ℕ. 

Be familiar with the concept of:


Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!). 
n! is the product of all positive integers less than or equal to n. 
Order of complexity
Content 
Additional information 

Be familiar with BigO notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in:


Be able to derive the time complexity of an algorithm. 
Limits of computation
Content 
Additional information 

Be aware that algorithmic complexity and hardware impose limits on what can be computed. 
Classification of algorithmic problems
Content 
Additional information 

Know that algorithms may be classified as being either:

Heuristic methods are often used when tackling intractable problems. 
Computable and noncomputable problems
Content 
Additional information 

Be aware that some problems cannot be solved algorithmically. 
Halting problem
Content 
Additional information 

Describe the Halting problem (but not prove it), that is the unsolvable problem of determining whether any program will eventually stop if given particular input. 

Understand the significance of the Halting problem for computation. 
The Halting problem demonstrates that there are some problems that cannot be solved by a computer. 
A model of computation
Turing machine
Content 
Additional information 

Be familiar with the structure and use of Turing machines that perform simple computations. 

Know that a Turing machine can be viewed as a computer with a single fixed program, expressed using:
One of the states is called a start state and states that have no outgoing transitions are called halting states. 
Exam questions will only be asked about Turing machines that have one tape that is infinite in one direction. 
Understand the equivalence between a transition function and a state transition diagram. 

Be able to:


Be able to explain the importance of Turing machines and the Universal Turing machine to the subject of computation. 
Turing machines provide a (general/formal) model of computation and provide a definition of what is computable. 