Content

Guidance

Resources

Simple Ideas of Algorithms

Correctness, finiteness and generality. Stopping conditions.

Candidates should appreciate that for a given input an algorithm produces a unique output. Candidates will not be required to write algorithms in examinations, but may be required to trace, correct, complete or amend a given algorithm, and compare or comment on the number of iterations required.

Bubble, shuttle, shell, quicksort algorithms. 

Candidates should appreciate the relative advantages of the different algorithms in terms of the number of iterations required.

Comment on number of comparisons and swaps.  Find an expression for the maximum number of comparisons when the shuttle sort algorithm is applied to a list of length of n.

Bubble Sort Checker - Excel by Debi Hand
Shuttle Sort Checker - Excel by Debi Hand

Graphs and Networks

Vertices, edges, edge weights, paths, cycles.

Adjacency/distance matrices

Connectedness.

Directed and undirected graphs.

Write down or interpret a matrix to represent a given graph.

For storage of graphs.

Degree of a vertex, odd and even vertices, Eulerian trails and Hamiltonian cycles.

Trees.

Draw all essentially different trees with 5 vertices.

Bi-partite graphs.

K_n and K_m,n

Conditions for planarity.

Spanning Tree Problems

Prim’s and Kruskal’s algorithms to find minimum spanning trees.

Relative advantage of the two algorithms. Greediness.

Minimum length spanning trees are also called minimum connectors.

Candidates will be expected to apply these algorithms in graphical, and for Prim’s algorithm also in tabular forms.

Essential that method and order of working is shown clearly on both graphical and tabular forms.

Candidates may be required to comment on the appropriateness of their solution in its context.

Matchings

Use of bipartite graphs.

Improvement of matching using an algorithm.

Use of an alternating path

Clear demonstration of method of working is required.

Shortest Paths in Networks

Dijkstra’s algorithm.

Problems involving shortest and quickest routes and paths of minimum cost. Including a labelling technique to identify the shortest path.

Networks may be given in graph or tabular form.

To include finding bounds of an individual edge to ensure a particular path is minimal.

Candidates may be required to comment on the appropriateness of their solution in its context.

Route Inspection Problem

Chinese Postman Problem.

Candidates should appreciate the significance of the odd vertices   They must show that they have considered all possible pairings of the odd vertices. Problems with more than four odd vertices will not be set.

Candidates may be required to comment on the appropriateness of their solution in its context.

Standards Unit Activity O1

Travelling Salesperson Problem

Conversion of a practical problem into the classical problem of finding a Hamiltonian cycle.

Determination of upper bounds by nearest neighbour algorithm.

Determination of lower bounds on route lengths using minimum spanning trees.

Modelling scheduling and other problems as TSPs.

By deleting a node then adding twice the shortest distance to the node or the sum of the two shortest edges and the length of the minimum spanning tree for the remaining graph.

Candidates may be required to comment on the appropriateness of their solution in its context.

Linear Programming

Candidates will be expected to formulate a variety of problems as linear programmes. They may be required to use up to a maximum of 3 decision variables.

Graphical solution of two-variable problems.

In the case of two decision variables candidates may be expected to plot a feasible region.  The significance of the objective line must be appreciated.

To include finding integer solutions

Candidates may be required to comment on the appropriateness of their solution in its context.

Mathematical modelling

The application of mathematical modeling to situations that relate to the topics covered in this module

Including the interpretation of results in context.