4 Theory of computation

What is an algorithm? (Spec 3.4.1.2)

A sequence of steps that can be followed to complete a task and that always terminates.

What is pseudocode and what is its main advantage?

A way of describing instructions independent of any programming language. It allows different programmers to communicate algorithms to one another.

What four standard constructs are used to express an algorithm in pseudo-code? (Spec 3.4.1.2)

Sequence, Assignment, Selection, and Iteration.

What three combining principles form the basis of all imperative programming languages? (Spec 3.1.1.2)

Sequence, Iteration (repetition), and Selection (choice).

What is assignment in pseudocode?

The process of giving a value to a variable or constant.

What is sequence in pseudocode?

Instructions that follow on from one another in the order that they appear.

What is selection in pseudocode?

The process of choosing an action to take based on the result of a comparison of values.

What is iteration in pseudocode?

The process of repeating an operation (e.g., using FOR and WHILE loops).

According to the spec, what 3 methods can be used to articulate how a program works and argue for its correctness/efficiency? (Spec 3.4.1.2)

1. Logical reasoning; 2. Test data; 3. User feedback.

What is representational abstraction? (Spec 3.4.1.3)

A representation arrived at by removing unnecessary details.

What is abstraction by generalisation or categorisation? (Spec 3.4.1.3)

A grouping by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type.

What is information hiding? (Spec 3.4.1.4)

The process of hiding all details of an object that do not contribute to its essential characteristics.

What is procedural abstraction? (Spec 3.4.1.5)

Abstracting away the actual values used in any particular computation to achieve a computational pattern or computational method (a procedure).

What is functional abstraction? (Spec 3.4.1.6)

Disregarding the particular computation method of a procedure, resulting in just a function where the computation method is hidden.

What is data abstraction? (Spec 3.4.1.7)

A methodology that enables us to isolate how a compound data object is used from the details of how it is constructed, hiding how details of data are actually represented.

What is problem abstraction / reduction? (Spec 3.4.1.8)

Removing details until the problem is represented in a way that is solvable, because the problem reduces to one that has already been solved.

What is procedural decomposition? (Spec 3.4.1.9)

1. Breaking a problem into a number of sub-problems; 2. So that each sub-problem accomplishes an identifiable task; 3. Which might itself be further subdivided.

What is composition abstraction? (Spec 3.4.1.10)

Combining procedures to form compound procedures (Procedural Composition), or combining data objects to form compound data structures like trees (Data Composition).

What is automation and how is it achieved? (Spec 3.4.1.11)

Putting models (abstractions of real-world phenomena) into action to solve problems. Achieved by: 1. Creating algorithms; 2. Implementing algorithms in code; 3. Implementing models in data structures; 4. Executing the code.

What is the goal of computer scientists when choosing details for abstract models? (Spec 3.4.1.11)

To determine the minimum amount of detail necessary to model messy, noisy, real-world objects/phenomena in order to solve a given problem to the required degree of accuracy.

When abstracting a problem into a graph, when is it more appropriate to use an adjacency matrix over an adjacency list? (June 2019)

When there are many edges between vertices (the graph/matrix is not sparse); When edges are frequently changed; When the presence/absence of specific edges needs to be tested frequently. (Any 2).

When representing an undirected graph as an adjacency matrix, only the top half of the matrix is needed. For which type of graph would the bottom half also need to be used? (June 2019)

A directed graph (or digraph).