29 Decision 1

 

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. The algorithm may be presented as a flow diagram.
Bubble, shuttle, shell, quicksort algorithms. Candidates should appreciate the relative advantages of the different algorithms in terms of the number of iterations required. When using the quicksort algorithm, the first number in each list will be taken as the pivot.
Vertices, edges, edge weights, paths, cycles, simple graphs.
Adjacency/distance matrices.For storage of graphs.
Connectedness.
Directed and undirected graphs.
Degree of a vertex, odd and even vertices, Eulerian trails and Hamiltonian cycles.
Trees.
Bipartite and complete graph.Use of the notations and

 

Prim's and Kruskal's algorithms to find minimum spanning trees. Relative advantage of the two algorithms. 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, form. Candidates may be required to comment on the appropriateness of their solution in its context.
Greediness.  

 

Use of bipartite graphs.  
Improvement of matching using an algorithm. Use of an alternating path.

 

Dijkstra's algorithm. Problems involving shortest and quickest routes and paths of minimum cost. Including a labelling technique to identify the shortest path. Candidates may be required to comment on the appropriateness of their solution in its context.

 

Chinese Postman problem.

Candidates should appreciate the significance of the odd vertices. Although problems with more than four odd vertices will not be set, candidates must be able to calculate the number of possible pairings for odd vertices.

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

 

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.

By deleting a node, then adding the two shortest distances to the node 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.

 

  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 variables, which may reduce to two variable requiring a graphical solution.
Graphical solution of two variable problems.

In the case of two decision variables candidates may be expected to plot a feasible region and objective line.
Candidates may be required to comment on the appropriateness of their solution in its context.

 

The application of mathematical modelling to situations that relate to the topics covered in this module. Including the interpretation of results in context.